面試經(jīng)典問題：
“逆置一個(gè)單鏈表”
鏈表結(jié)構(gòu)為：
1 typedef struct node
2 {
3 int data;
4 struct node *next;
5 } NODE;
由于題目限制比較少，所以就需要仔細(xì)考慮，鏈表是否有環(huán)？如果鏈表有
小環(huán)那么鏈表將不可逆置，因?yàn)榄h(huán)的入口節(jié)點(diǎn)有兩個(gè)前驅(qū)節(jié)點(diǎn)。所有首先應(yīng)該判斷鏈表是否有小環(huán)，如果沒有小環(huán)才能對鏈表進(jìn)行逆置。而如何判斷鏈表是否有環(huán)？
一種方法是用一個(gè)指針遍歷鏈表，每遍歷一個(gè)節(jié)點(diǎn)便對節(jié)點(diǎn)做標(biāo)記，如果節(jié)點(diǎn)走到NULL，則說明沒有環(huán)，如果遇到了已經(jīng)做過標(biāo)記的節(jié)點(diǎn)，則說明有環(huán)，且這個(gè)做標(biāo)記的節(jié)點(diǎn)就是入口。但是
如果不允許對節(jié)點(diǎn)做標(biāo)記該怎么辦呢？另外一種方法是對每個(gè)節(jié)點(diǎn)的地址做hash，每次訪問一個(gè)節(jié)點(diǎn)的時(shí)候都查看hash表，如果該節(jié)點(diǎn)的地址不在hash表中，則說明該節(jié)點(diǎn)未被訪問，直到遇到NULL或者遇到某個(gè)節(jié)點(diǎn)在hash表中有記錄，則該節(jié)點(diǎn)則是環(huán)的入口。該算法同樣有很大的弊病，需要大量內(nèi)存，因?yàn)楣?jié)點(diǎn)的地址是32位的。下面提供
第三種方法：采用兩個(gè)指針（假設(shè)為p1,p2），初始情況下都指向鏈表頭，之后p2每次走2步，p1每次走1步，當(dāng)p1和p2相交的時(shí)候則說明有環(huán)，否則當(dāng)p2走到NULL的時(shí)候則說明無環(huán)，證明也比較簡單。那么如何找到環(huán)的入口點(diǎn)呢？這里提供一種方法：當(dāng)確定有環(huán)后，p2在相交處，p1重新指向鏈表開頭，然后每次兩個(gè)指針都各走一步，這樣兩個(gè)指針再次相遇的時(shí)候便是環(huán)的入口處。證明如下：
假設(shè)從鏈表頭到環(huán)的入口長度為l，環(huán)的周長為r，p1和p2相遇的點(diǎn)距離環(huán)入口為x
則我們有以下結(jié)論：
1、第一次相交的時(shí)候p1還沒有走完整條鏈表，而p2則在鏈表的環(huán)內(nèi)轉(zhuǎn)了n圈
2、第一次相交的時(shí)候p2走的距離是p1的兩倍，因?yàn)閜2每次走兩步而p1每次走一步
這樣我們就得到如下公式：
2(x + l) = l + x + nr
則可以得到l = nr - x
這樣我們將p1重新放到鏈表頭開始走，那么當(dāng)p1節(jié)點(diǎn)走了l距離的時(shí)候，可以知道p2也走了l距離，而l = nr - x，所以p2走了nr - x，而p2從相交點(diǎn)開始走的，該點(diǎn)距離環(huán)入口處為x，這樣可以知道當(dāng)p2走了nr - x步后正好就到了環(huán)的入口，而p1此時(shí)也正在環(huán)的入口，可以知道p1和p2正好相遇，證畢。
下面一段代碼是用來判斷鏈表是否有環(huán)的，包括大環(huán)和小環(huán)：
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 }
其實(shí)對于單鏈表的操作，絕大部分都需要先判斷鏈表是否為空，然后判斷鏈表是否呦環(huán)，有大環(huán)和有小環(huán)在有寫問題的處理方式未必一樣，比如對于鏈表逆置，鏈表為空、或者鏈表有大環(huán)，鏈表都可以正常被逆置，而如果是有小環(huán)的鏈表，則鏈表不可被逆置。
下面看鏈表逆置的代碼，其中調(diào)用了上面判斷鏈表是否有環(huán)的函數(shù)：
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 }
下面一段代碼是用來對單鏈表測長的，也許要對單鏈表判斷是否有環(huán)：
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 }
而下面一段代碼是用來判斷兩個(gè)單鏈表是否相交的，該問題有點(diǎn)復(fù)雜：
首先，如果其中任意一條鏈表為空，則不可能相交
其次，如果兩個(gè)鏈表都沒有環(huán)，則判斷鏈表的尾元素是否相同
再次，如果兩個(gè)鏈表一個(gè)呦環(huán)，一個(gè)無環(huán)，則不可能相交
最后，如果兩個(gè)鏈表均有環(huán)，則從其中一個(gè)入口處開始走一圈，如果中間和另一環(huán)的入口相遇則說明兩鏈表相交
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 //兩個(gè)鏈表都沒有環(huán)
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 //兩個(gè)鏈表都有環(huán)
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 //一個(gè)有環(huán)一個(gè)無環(huán)
22 return 0;
23 }
下面是合并兩個(gè)有序鏈表，該問題也需要考慮全面，既然有序，則不需要考慮是否有環(huán)，但是兩個(gè)鏈表是否都是遞增或者遞減則需要考慮，我們在此不判斷兩個(gè)鏈表一個(gè)一個(gè)遞增一個(gè)遞減的情況。下面代碼第三個(gè)參數(shù)代表鏈表單調(diào)性，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 }
對于將鏈表排序也有一個(gè)非常巧妙的地方，我們知道普通數(shù)組排序一般采用快排、堆排或者歸并排序，而在鏈表上卻不那么容易，因?yàn)殒湵聿荒苤苯佑盟饕齺韺ぶ?，而是采用指針地址索引，所以快排、堆排都失去了?yōu)勢，但是歸并排序卻如魚得水，而且在數(shù)組歸并排序當(dāng)中被詬病的空間復(fù)雜度O(n)在鏈表排序當(dāng)中也降為O(1)。這里面還用到了一個(gè)小技巧，就是如何找到鏈表的中間元素，這里采用兩個(gè)指針一快一慢的方法：
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 }
找到無環(huán)鏈表倒數(shù)第k個(gè)節(jié)點(diǎn)，該問題比較簡單，只需要先設(shè)一個(gè)指針p2預(yù)先走k步，然后再讓p2每次走一步，同時(shí)在鏈表開頭也有一指針p1每次走一步，這樣，當(dāng)p2走到尾部的時(shí)候p1則恰好是倒數(shù)第k個(gè)節(jié)點(diǎn)：
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 }
關(guān)于鏈表問題暫時(shí)寫到此。