面試經典問題：
“逆置一個單鏈表”
鏈表結構為：
1 typedef struct node
2 {
3 int data;
4 struct node *next;
5 } NODE;
由于題目限制比較少，所以就需要仔細考慮，鏈表是否有環？如果鏈表有
小環那么鏈表將不可逆置，因為環的入口節點有兩個前驅節點。所有首先應該判斷鏈表是否有小環，如果沒有小環才能對鏈表進行逆置。而如何判斷鏈表是否有環？
一種方法是用一個指針遍歷鏈表，每遍歷一個節點便對節點做標記，如果節點走到NULL，則說明沒有環，如果遇到了已經做過標記的節點，則說明有環，且這個做標記的節點就是入口。但是
如果不允許對節點做標記該怎么辦呢？另外一種方法是對每個節點的地址做hash，每次訪問一個節點的時候都查看hash表，如果該節點的地址不在hash表中，則說明該節點未被訪問，直到遇到NULL或者遇到某個節點在hash表中有記錄，則該節點則是環的入口。該算法同樣有很大的弊病，需要大量內存，因為節點的地址是32位的。下面提供
第三種方法：采用兩個指針（假設為p1,p2），初始情況下都指向鏈表頭，之后p2每次走2步，p1每次走1步，當p1和p2相交的時候則說明有環，否則當p2走到NULL的時候則說明無環，證明也比較簡單。那么如何找到環的入口點呢？這里提供一種方法：當確定有環后，p2在相交處，p1重新指向鏈表開頭，然后每次兩個指針都各走一步，這樣兩個指針再次相遇的時候便是環的入口處。證明如下：
假設從鏈表頭到環的入口長度為l，環的周長為r，p1和p2相遇的點距離環入口為x
則我們有以下結論：
1、第一次相交的時候p1還沒有走完整條鏈表，而p2則在鏈表的環內轉了n圈
2、第一次相交的時候p2走的距離是p1的兩倍，因為p2每次走兩步而p1每次走一步
這樣我們就得到如下公式：
2(x + l) = l + x + nr
則可以得到l = nr - x
這樣我們將p1重新放到鏈表頭開始走，那么當p1節點走了l距離的時候，可以知道p2也走了l距離，而l = nr - x，所以p2走了nr - x，而p2從相交點開始走的，該點距離環入口處為x，這樣可以知道當p2走了nr - x步后正好就到了環的入口，而p1此時也正在環的入口，可以知道p1和p2正好相遇，證畢。
下面一段代碼是用來判斷鏈表是否有環的，包括大環和小環：
1 node *list_isloop(node *head) {
2 if (head == NULL) return head;
3 node *p1 = head, *p2 = head;
4 do {
5 p2 = p2->next;
6 if (p2 == NULL || p2 == head) return p2;
7 p2 = p2->next;
8 if (p2 == NULL || p2 == head) return p2;
9 p1 = p1->next;
10 } while (p1 != p2);
11 p1 = head;
12 while (p1 != p2) { p1 = p1->next; p2 = p2->next; }
13 return p2;
14 }
其實對于單鏈表的操作，絕大部分都需要先判斷鏈表是否為空，然后判斷鏈表是否呦環，有大環和有小環在有寫問題的處理方式未必一樣，比如對于鏈表逆置，鏈表為空、或者鏈表有大環，鏈表都可以正常被逆置，而如果是有小環的鏈表，則鏈表不可被逆置。
下面看鏈表逆置的代碼，其中調用了上面判斷鏈表是否有環的函數：
1 node *list_reverse(node *head) {
2 if (head == NULL || head->next == NULL) return head;
3 node *entry = list_isloop(head);
4 if (entry != NULL && entry != head) return NULL;
5 node *p1 = head, *p2 = p1->next, *p3 = p2->next;
6 p1->next = NULL;
7 while (p3 && p3 != head) {
8 p2->next = p1;
9 p1 = p2;
10 p2 = p3;
11 p3 = p3->next;
12 }
13 p2->next = p1;
14 return p2;
15 }
下面一段代碼是用來對單鏈表測長的，也許要對單鏈表判斷是否有環：
1 int list_len(node *head) {
2 int len = 0;
3 node *p = head, *entry = NULL;
4 if (head == NULL) return 0;
5 entry = list_isloop(head);
6 while (p != entry) { ++len; p = p->next; }
7 if (entry != NULL)
8 do { ++len; p = p->next; } while (p != entry);
9 return len;
10 }
而下面一段代碼是用來判斷兩個單鏈表是否相交的，該問題有點復雜：
首先，如果其中任意一條鏈表為空，則不可能相交
其次，如果兩個鏈表都沒有環，則判斷鏈表的尾元素是否相同
再次，如果兩個鏈表一個呦環，一個無環，則不可能相交
最后，如果兩個鏈表均有環，則從其中一個入口處開始走一圈，如果中間和另一環的入口相遇則說明兩鏈表相交
1 int list_intersecting(node *head1, node *head2) {
2 if (head1 == NULL || head2 == NULL) return 0;
3 node *entry1 = list_isloop(head1);
4 node *entry2 = list_isloop(head2);
5 //兩個鏈表都沒有環
6 if (entry1 == NULL && entry2 == NULL) {
7 while (head1->next != NULL) head1 = head1->next;
8 while (head2->next != NULL) head2 = head2->next;
9 if (head1 == head2) return 1;
10 return 0;
11 }
12 //兩個鏈表都有環
13 else if (entry1 != NULL && entry2 != NULL) {
14 node *tmp = entry1;
15 while (tmp->next != entry1) {
16 if (tmp == entry2) return 1;
17 tmp = tmp->next;
18 }
19 if (tmp == entry2) return 1;
20 }
21 //一個有環一個無環
22 return 0;
23 }
下面是合并兩個有序鏈表，該問題也需要考慮全面，既然有序，則不需要考慮是否有環，但是兩個鏈表是否都是遞增或者遞減則需要考慮，我們在此不判斷兩個鏈表一個一個遞增一個遞減的情況。下面代碼第三個參數代表鏈表單調性，flag = 0代表遞增，flag != 0代表遞減：
1 node *list_merge(node *head1, node *head2, int flag) {
2 if (head1 == NULL) return head2;
3 if (head2 == NULL) return head1;
4 flag = !!flag;
5 node *head = NULL;
6 if (flag == 0) {
7 if (head1->data < head2->data) {
8 head = head1;
9 head->next = list_merge(head1->next, head2, flag);
10 }
11 else {
12 head = head2;
13 head->next = list_merge(head1, head2->next, flag);
14 }
15 }
16 else {
17 if (head1->data > head2->data) {
18 head = head1;
19 head->next = list_merge(head1->next, head2, flag);
20 }
21 else {
22 head = head2;
23 head->next = list_merge(head1, head2->next, flag);
24 }
25 return head;
26 }
27 }
對于將鏈表排序也有一個非常巧妙的地方，我們知道普通數組排序一般采用快排、堆排或者歸并排序，而在鏈表上卻不那么容易，因為鏈表不能直接用索引來尋址，而是采用指針地址索引，所以快排、堆排都失去了優勢，但是歸并排序卻如魚得水，而且在數組歸并排序當中被詬病的空間復雜度O(n)在鏈表排序當中也降為O(1)。這里面還用到了一個小技巧，就是如何找到鏈表的中間元素，這里采用兩個指針一快一慢的方法：
1 node *list_sort(node *head, int flag) {
2 if (head == NULL || head->next == NULL) return head;
3 flag = !!flag;
4 node *p1 = head, *p2 = head;
5 while (p2 != NULL) {
6 if ((p2 = p2->next) == NULL) break;
7 if ((p2 = p2->next) == NULL) break;
8 p1 = p1->next;
9 }
10 p2 = p1->next;
11 p1->next = NULL;
12 p1 = list_sort(head, flag);
13 p2 = list_sort(p2, flag);
14 return list_merge(p1, p2, flag);
15 }
找到無環鏈表倒數第k個節點，該問題比較簡單，只需要先設一個指針p2預先走k步，然后再讓p2每次走一步，同時在鏈表開頭也有一指針p1每次走一步，這樣，當p2走到尾部的時候p1則恰好是倒數第k個節點：
1 node *list_ktailed(node *head, int k) {
2 if (k < 0) return NULL;
3 int i = 0;
4 node *p1 = head, *p2 = head;
5 for (; i < k; ++i) {
6 if (p2 == NULL) return NULL;
7 p2 = p2->next;
8 }
9 while (p2 != NULL) { p2 = p2->next; p1 = p1->next; }
10 return p1;
11 }
關于鏈表問題暫時寫到此。