反转链表小算法

基本思想是，从链表的第二个结点(如果存在的话)开始，依次插入到链表的头结点后面，即作为第一个结点，直至表尾，此时链表反转工作已经完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <iostream>
#include <cassert>
using namespace std;
struct Node
{
	Node(int n = 0):data(n){}
	int data;
	Node* next;
}; 
void reverse(Node * T)
{
	assert(T); //~ 表头非空
	Node* p = T->next, *t;
	if(p)
	{	//~ 将第一个结点，即未来的表尾next域置空
		t = p->next;
		p->next = NULL;
		p = t;
	}
	while(p)
	{	//~ 将余下结点依次插入表头
		t = p->next;
		p->next = T->next;
		T->next = p;
		p = t;
	}
}
 
//~ 测试代码
int main()
{
	Node *head = new Node, *t = head;
	for(int i = 0; i < 10; ++i)
	{
		t->next = new Node(i);
		t = t->next;
	}
	t->next = NULL;
 
	Node * p = head->next;
	reverse(head);
	while(p)
	{
		cout<<p->data<<endl;
		p = p->next;
	}
 
	return 0;
}
Tags: ,.
Filed under: 之语言特性 By dutor @ August 17th, 2009, 64 views Comments (3)
你好！除了代码，此处没有多少原创之物，皆为本人搜集、整理、总结之记录与心得，欢迎转载分享！转载时请尽量注明出处，将不胜感激。祝你健康、快乐！
«
»
Home

RFC: Request For Comments. Orz..

Name(required)
Mail (required),(will not be published)

RFC: Request For Comments. Orz..

Website(recommended)