反转单向链表

单向链表的反转分两种情况，一种是带头结点的单向链表的反转，另一种是不带头结点的单向链表的反转

一、不带头结点的单向链表的反转

　　不带头结点的单向链表反转需要三个指针，一个指针存储当前节点，一个存储当前节点的前一个节点，最后一个指针存储当前节点的下一个指针，每次反转当前节点的指针指向，一次往后遍历链表。

 1 NODE *ReverseWithouHead(NODE *&head)
 2 {
 3     assert (head != NULL);
 4 
 5     // 不带头结点的单向链表的反转
 6 
 7     if (NULL == (head->next))
 8     {
 9         return (head);
10     }
11 
12     NODE *pre = head;
13     NODE *cur = head->next;
14     NODE *next = NULL;
15 
16     while (cur != NULL)
17     {
18         next = cur->next;
19         cur->next = pre;
20         pre = cur;
21         cur=next;
22     }
23 
24     head->next = NULL;
25     head = pre;
26 
27     return (head);
28 }

二、带头结点的单向链表的反装

　　带头结点的单向链表的反转只需要两个指针，把后面的节点一次往前面插入到头结点的后面即可

 1 NODE *Reverse(NODE *head)
 2 {
 3     assert (head != NULL);
 4 
 5     // 带头结点的单向链表的反转
 6 
 7     NODE *p1 = head->next;
 8 
 9     if ((NULL == p1) || (NULL == (p1->next)))
10     {
11         return head;
12     }
13 
14     NODE *p2 = p1->next;
15 
16     while ((NULL != p1) && (NULL != p2))
17     {
18         p1->next = p2->next;
19         p2->next = head->next;
20         head->next = p2;
21         p2 = p1->next;
22     }
23 
24     return head;
25 }