以下給出鏈表結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)：
1 typedef struct _list_node
2 {
3 double keyVal;
4 struct _list_node *next;
5 }ListNode;
Q1
單鏈表的反序
Code
1 ListNode* reverseList(ListNode* head)
2 {
3 ListNode *p1, *p2 , *p3;
4 //鏈表為空，或是單結(jié)點(diǎn)鏈表直接返回頭結(jié)點(diǎn)
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 }
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 }
思路分析：
單鏈表的一個(gè)比較大的特點(diǎn)用一句廣告語來說就是“不走回頭路”，不能實(shí)現(xiàn)隨機(jī)存取（random access）。如果我們想要找一個(gè)數(shù)組a的中間元素，直接a[len/2]就可以了，但是鏈表不行，因?yàn)橹挥衋[len/2 - 1] 知道a[len/2]在哪兒，其他人不知道。因此，如果按照數(shù)組的做法依樣畫葫蘆，要找到鏈表的中點(diǎn)，我們需要做兩步（1）知道鏈表有多長（2）從頭結(jié)點(diǎn)開始順序遍歷到鏈表長度的一半的位置。這就需要1.5n（n為鏈表的長度）的時(shí)間復(fù)雜度了。有沒有更好的辦法呢？有的。想法很簡單：兩個(gè)人賽跑，如果A的速度是B的兩倍的話，當(dāng)A到終點(diǎn)的時(shí)候，B應(yīng)該剛到中點(diǎn)。這只需要遍歷一遍鏈表就行了，還不用計(jì)算鏈表的長度。
上面的代碼就體現(xiàn)了這個(gè)想法。
Q3 鏈表排序
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ù)組排序時(shí)性能非常好的算法，在鏈表只能“順序訪問”的魔咒下無法施展能力；但是歸并排序卻如魚得水，非但保持了它O(nlogn)的時(shí)間復(fù)雜度，而且它在數(shù)組排序中廣受詬病的空間復(fù)雜度在鏈表排序中也從O(n)降到了O(1)。真是好得不得了啊，哈哈。以上程序是遞推法的程序，另外值得一說的是看看那個(gè)時(shí)間復(fù)雜度，是不是有點(diǎn)眼熟？對！這就是分治法的時(shí)間復(fù)雜度，歸并排序又是divide and conquer。
Q4 判斷一個(gè)單鏈表是否有環(huán)
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專家編程》中的題了。其實(shí)算法也有很多，比如說：我覺得進(jìn)行對訪問過的結(jié)點(diǎn)進(jìn)行標(biāo)記這個(gè)想法也不錯(cuò)，而且在樹遍歷等場合我們也經(jīng)常使用。但是在不允許做標(biāo)記的場合就無法使用了。在種種限制的條件下，就有了上面的這種算法，其實(shí)思想很簡單：就像兩個(gè)人在操場上跑步一樣，只要有個(gè)人的速度比另一個(gè)人的速度快一點(diǎn)，他們肯定會(huì)有相遇的時(shí)候的。不過帶環(huán)鏈表與操場又不一樣，帶環(huán)鏈表的狀態(tài)是離散的，所以選擇走得快的要比走得慢的快多少很重要。比如說這里，如果一個(gè)指針一次走三步，一個(gè)指針一次走一步的話，很有可能它們雖然在一個(gè)環(huán)中但是永遠(yuǎn)遇不到，這要取決于環(huán)的大小以及兩個(gè)指針初始位置相差多少了。呵呵。你能看出兩個(gè)指針的速度應(yīng)該滿足什么關(guān)系才能在有環(huán)的情況下相遇嗎？如果你知道，不妨跟我討論一下，呵呵。