Code
 1 ListNode* reverseList(ListNode* head)
 2 {
 3     ListNode *p1, *p2 , *p3;
 4     //鏈表為空，或是單結(jié)點鏈表直接返回頭結(jié)點
 5     if (head == NULL || head->next == NULL)
 6     {
 7         return head;
 8     }
 9     p1 = head;
10     p2 = head->next;
11     while (p2 != NULL)
12     {
13         p3 = p2->next;
14         p2->next = p1;
15         p1 = p2;
16         p2 = p3;
17     }
18     head->next = NULL;
19     head = p1;
20 
21     return head;
22 }

Q2 找出鏈表的中間元素

Code
 1 ListNode* find_midlist(ListNode* head)
 2 {
 3     ListNode *p1, *p2;
 4     
 5     if (head == NULL || head->next == NULL)
 6     {
 7         return head;
 8     }
 9     p1 = p2 = head;
10     while (1)
11     {
12         if (p2->next != NULL && p2->next->next != NULL)
13         {
14             p2 = p2->next->next;
15             p1 = p1->next;
16         }
17         else
18         {
19             break;
20         }
21     }
22     return p1;
23 }

思路分析：

 單鏈表的一個比較大的特點用一句廣告語來說就是“不走回頭路”，不能實現(xiàn)隨機存取（random access）。如果我們想要找一個數(shù)組a的中間元素，直接a[len/2]就可以了，但是鏈表不行，因為只有a[len/2 - 1] 知道a[len/2]在哪兒，其他人不知道。因此，如果按照數(shù)組的做法依樣畫葫蘆，要找到鏈表的中點，我們需要做兩步（1）知道鏈表有多長（2）從頭結(jié)點開始順序遍歷到鏈表長度的一半的位置。這就需要1.5n（n為鏈表的長度）的時間復(fù)雜度了。有沒有更好的辦法呢？有的。想法很簡單：兩個人賽跑，如果A的速度是B的兩倍的話，當(dāng)A到終點的時候，B應(yīng)該剛到中點。這只需要遍歷一遍鏈表就行了，還不用計算鏈表的長度。

 上面的代碼就體現(xiàn)了這個想法。

Code
 1 double cmp(ListNode *p ,ListNode *q)
 2 {return (p->keyVal - q->keyVal);}
 3 
 4 ListNode* mergeSortList(ListNode *head)
 5 {
 6     ListNode *p, *q, *tail, *e;
 7     int nstep = 1;
 8     int nmerges = 0;
 9     int i;
10     int psize, qsize;
11     if (head == NULL || head->next == NULL)
12     {return head;}
13     while (1)
14     {   p = head;
15         tail = NULL;
16         nmerges = 0;
17         while (p)
18         {   nmerges++;  q = p;  psize = 0;
19             for (i = 0; i < nstep; i++){
20                 psize++;
21                 q = q->next;
22                 if (q == NULL)break;
23 }
24             qsize = nstep;
25             while (psize >0 || (qsize >0 && q))
26 {
27                 if (psize == 0 ){e = q; q = q->next; qsize--;}
28                 elseif (q == NULL || qsize == 0){e = p; p = p->next; psize--;}
29                 elseif (cmp(p,q) <= 0){e = p; p = p->next; psize--;}
30                 else{e = q; q = q->next; qsize--;}
31                 if (tail != NULL){tail->next = e;}
32                 else{head = e;}
33                 tail = e;
34               }
35             p = q;
36         }
37         tail->next = NULL;
38         if (nmerges <= 1){return head;}
39         else{nstep <<= 1;}
40     }
41 }

思路分析：

  鏈表排序最好使用歸并排序算法。堆排序、快速排序這些在數(shù)組排序時性能非常好的算法，在鏈表只能“順序訪問”的魔咒下無法施展能力；但是歸并排序卻如魚得水，非但保持了它O(nlogn)的時間復(fù)雜度，而且它在數(shù)組排序中廣受詬病的空間復(fù)雜度在鏈表排序中也從O(n)降到了O(1)。真是好得不得了啊，哈哈。以上程序是遞推法的程序，另外值得一說的是看看那個時間復(fù)雜度，是不是有點眼熟？對！這就是分治法的時間復(fù)雜度，歸并排序又是divide and conquer。

Code
 1 int is_looplist (ListNode *head)
 2 {
 3     ListNode *p1, *p2;
 4     p1 = p2 = head;
 5 
 6     if (head == NULL || head->next == NULL)
 7     {
 8         return 0;
 9     }
10 
11     while (p2->next != NULL && p2->next->next != NULL)
12     {
13         p1 = p1->next;
14         p2 = p2->next->next;
15         if (p1 == p2)
16         {
17             return 1;
18         }
19     }
20 
21     return 0;
22 
23 }

思路分析：

  這道題是《C專家編程》中的題了。其實算法也有很多，比如說：我覺得進行對訪問過的結(jié)點進行標(biāo)記這個想法也不錯，而且在樹遍歷等場合我們也經(jīng)常使用。但是在不允許做標(biāo)記的場合就無法使用了。在種種限制的條件下，就有了上面的這種算法，其實思想很簡單：就像兩個人在操場上跑步一樣，只要有個人的速度比另一個人的速度快一點，他們肯定會有相遇的時候的。不過帶環(huán)鏈表與操場又不一樣，帶環(huán)鏈表的狀態(tài)是離散的，所以選擇走得快的要比走得慢的快多少很重要。比如說這里，如果一個指針一次走三步，一個指針一次走一步的話，很有可能它們雖然在一個環(huán)中但是永遠(yuǎn)遇不到，這要取決于環(huán)的大小以及兩個指針初始位置相差多少了。呵呵。你能看出兩個指針的速度應(yīng)該滿足什么關(guān)系才能在有環(huán)的情況下相遇嗎？如果你知道，不妨跟我討論一下，呵呵。