鏈表的經(jīng)典問題

?

?

如何判斷兩個(gè)單鏈表是否相交，如果相交，找出交點(diǎn)（兩個(gè)鏈表都不存在環(huán)）

如果兩個(gè)單鏈表相交，那應(yīng)該呈“Y”字形，也就是從交點(diǎn)以后的部分是兩個(gè)鏈表的公共節(jié)點(diǎn)。

所以，判斷是否相交只要看兩個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)是否為同一個(gè)即可。

那么如何找到交點(diǎn)呢？設(shè)兩個(gè)單鏈表的長度分別為L1、L2，（假設(shè)L1>L2），則(L1-L2)的值就是交匯之前兩個(gè)鏈表的長度差；

因此，只有讓更長的鏈表先走L1-L2步，然后兩個(gè)鏈表開始一起走，如果某次走到一個(gè)相同的節(jié)點(diǎn)，該節(jié)點(diǎn)即為交點(diǎn)。

?

C代碼實(shí)現(xiàn)：

typedef struct _ListNode {int data;struct _ListNode *next; } ListNode;static int GetListLength(ListNode *T) {int n;for(n=0; T; n++) {T = T->next; } return n; }static ListNode* FindFirstCommonNode(ListNode *T1, ListNode *T2) {int i;int n1 = GetListLength(T1);int n2 = GetListLength(T2);// T1 always own longer listif (n1 < n2) {return FindFirstCommonNode(T2, T1);} for (i=0; i<n1-n2; i++) {T1 = T1->next;} while (T1 && T1 != T2) {T1 = T1->next;T2 = T2->next; } return T1; }

?

該問題還有一種思路，就是將其中一個(gè)鏈表首尾相連，然后檢測另外一個(gè)鏈表是否有環(huán)，如果存在環(huán)，則兩個(gè)鏈表相交。

?

判斷一個(gè)鏈表是否有環(huán)，并找到環(huán)的入口點(diǎn)

如果一個(gè)單鏈表有環(huán)，那應(yīng)該呈“6”字形。

設(shè)置兩個(gè)指針(fast, slow)，初始值都指向頭節(jié)點(diǎn)，slow每次前進(jìn)一步，fast每次前進(jìn)二步，如果鏈表存在環(huán)，則fast必定先進(jìn)入環(huán)，而slow后進(jìn)入環(huán)，兩個(gè)指針必定 相遇：如果鏈表是呈"O"字形，則slow剛好遍歷完一次的時(shí)候，與fast相遇；如果呈“6”字形，則更早相遇。

當(dāng)fast若與slow相遇時(shí)，slow還沒有遍歷完鏈表，而fast已經(jīng)在環(huán)內(nèi)循環(huán)了n圈(1<=n)。假設(shè)slow走了s步，則 fast走了2s步（fast步數(shù)還等于s 加上在環(huán)上多轉(zhuǎn)的n圈），設(shè)環(huán)長為r，則：

2s = s + nr，簡化為?s= nr

s = x + y，x為鏈表起點(diǎn)到環(huán)入口點(diǎn)的距離，y是slow在環(huán)內(nèi)走過的距離；

可以得到 x = y - s = y - nr，從鏈表頭、相遇點(diǎn)分別設(shè)一個(gè)指針(p1, p2)，每次各走一步，當(dāng)p1走過距離x時(shí)到達(dá)入口點(diǎn)，而p2走過的距離為y-nr，y是相遇點(diǎn)與入口點(diǎn)的距離，因此y也走到了入口點(diǎn)，也就是說p1、p2在環(huán)入口點(diǎn)相遇了。

?

C代碼實(shí)現(xiàn)：

static ListNode* FindLoopPort(ListNode *Head) { ListNode *slow = Head; ListNode *fast = Head; // 找到相遇點(diǎn)while ( fast && fast->next ) { slow = slow->next; fast = fast->next->next; if ( slow == fast ) break; } if (fast == NULL || fast->next == NULL) return NULL; // 找到環(huán)入口點(diǎn)slow = Head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; }

?

?

求一個(gè)單鏈表（無環(huán)）的中間節(jié)點(diǎn)

設(shè)置兩個(gè)指針(fast, slow)，初始值都指向頭節(jié)點(diǎn)，slow每次前進(jìn)一步，fast每次前進(jìn)二步，當(dāng)fast走到末尾時(shí)，slow剛好指向中間節(jié)點(diǎn)。

?

假如鏈表長度為N，如何返回鏈表的倒數(shù)第K個(gè)結(jié)點(diǎn)

思路：用兩個(gè)指針，指針P1先走K-1步，然后指針P2才開始走，當(dāng)指針P1遍歷完鏈表時(shí)，P2還剩K個(gè)結(jié)點(diǎn)沒有遍歷。

?

實(shí)現(xiàn)如下：

ListNode *FindLastKNode(ListNode *Head, int K) {if (NULL == Head)return NULL;ListNode *T1 = Head;ListNode *T2 = Head;while (T1 && --K) T1 = T1->next; if (K) // here, K must be 0 return NULL; while (T1->next) { T1 = T1->next; T2 = T2->next; } return T2; }

?

?

在O(1)時(shí)間刪除鏈表結(jié)點(diǎn)

在鏈表中刪除一個(gè)結(jié)點(diǎn)，最常規(guī)的做法是遍歷鏈表，找到要?jiǎng)h除的結(jié)點(diǎn)后再刪除，這種做法的時(shí)間復(fù)雜度是O(n)；
換一種思路，根據(jù)待刪除結(jié)點(diǎn)A，可以知道其下一個(gè)結(jié)點(diǎn)是B=A->next，將結(jié)點(diǎn)B值拷貝給A，然后刪除B即可。
這種方法需要考慮一種特殊情況，A如果是尾結(jié)點(diǎn)，則B不存在，此時(shí)仍需要遍歷鏈表一次。

?

C代碼實(shí)現(xiàn)：

void DeleteNode(ListNode* Head, ListNode *pDel) {if (NULL == pDel || NULL == Head)return;ListNode *p = Head;if (NULL == pDel->next) { // pDel is the last nodewhile (pDel != p->next)p = p->next;p->next = NULL;free(pDel);
} else {p = pDel->next;pDel->next = p->next;pDel->data = p->data;free(p);} }

?

?

如何逆序輸出一個(gè)單鏈表

方法一：從頭到尾遍歷鏈表，每經(jīng)過一個(gè)結(jié)點(diǎn)的時(shí)候，把該結(jié)點(diǎn)放到一個(gè)棧中；當(dāng)遍歷完整個(gè)鏈表后，再從棧頂開始輸出結(jié)點(diǎn)的值。
該方法需要維護(hù)一個(gè)額外的棧，實(shí)現(xiàn)起來比較麻煩。我們注意到遞歸本質(zhì)上就是一個(gè)棧結(jié)構(gòu)，所以，也可以用遞歸來實(shí)現(xiàn)反向輸出鏈表。

方法二：也就是說，每訪問到一個(gè)結(jié)點(diǎn)的時(shí)候，先遞歸輸出它后面的結(jié)點(diǎn)，再輸出該結(jié)點(diǎn)自身。

?

C代碼實(shí)現(xiàn)：

void ReversePrint(ListNode *Head) {if (Head) {if (Head->next) {ReversePrint(Head->next);}printf("%d ", Head->data);} }

?

?

?

如何反轉(zhuǎn)一個(gè)單鏈表

?利用輔助指針就地修改節(jié)點(diǎn)的next域，代碼如下：

static ListNode *ReverseList(ListNode *Head) {ListNode *pNode = Head;ListNode *pNext = NULL;ListNode *pPrev = NULL;while (pNode) {pNext = pNode->next; if (NULL == pNext) // meet the endHead = pNode;pNode->next = pPrev;pPrev = pNode;pNode = pNext;} return Head; }

?

遞歸 的實(shí)現(xiàn)方法：

static void ReverseList2(ListNode** Head) {ListNode *p = *Head;if (!p) return;ListNode* rest = p->next;if (!rest) return;ReverseList2(&rest);rest->next = p;p->next = NULL; }

?

?

鏈表的排序

歸并排序?qū)崿F(xiàn)的時(shí)間復(fù)雜度為 nlgn，

struct ListNode* Merge(struct ListNode* p1, struct ListNode *p2) {if (!p1) return p2;if (!p2) return p1;if (p1->val > p2->val) {p2->next = Merge(p1, p2->next);return p2;} else {p1->next = Merge(p1->next, p2);return p1;}}struct ListNode* sortList(struct ListNode* head) {if (!head || !head->next) return head;struct ListNode *h1, *h2;struct ListNode *p1 = head, *p2 = head, *p = head;while (p2 && p2->next) {p = p1;p1 = p1->next;p2 = p2->next->next;}p->next = NULL;h1 = sortList(p1);h2 = sortList(head);return Merge(h1, h2); }

以上遞歸的實(shí)現(xiàn)會占用lgN的空間（遞歸壓棧），非遞歸的實(shí)現(xiàn)如下：

?

?

復(fù)雜鏈表的復(fù)制

假設(shè)有一個(gè)復(fù)雜鏈表，它除了有一個(gè)next指針外，還有一個(gè)other指針，指向鏈表中的任一結(jié)點(diǎn)或者NULL，

typedef struct _ListNode {int data;struct _ListNode *next;struct _ListNode *other; } ListNode;

?

如下圖，是一個(gè)含義5個(gè)節(jié)點(diǎn)的該類型的復(fù)雜鏈表，實(shí)線表示next指針，虛線表示other指針，NULL指針未標(biāo)出。

?

最簡單的方法是，先復(fù)制所有節(jié)點(diǎn)，并用next指針鏈接起來，然后假設(shè)原始鏈表的某節(jié)點(diǎn)N的other指針指向節(jié)點(diǎn)S，由于S的位置可能在N的前面，也可能在N的后面，所以要定位N的位置需要從原始鏈表的頭節(jié)點(diǎn)開始找，直到確認(rèn)節(jié)點(diǎn)S在鏈表中的位置為s；然后在復(fù)制鏈表上節(jié)點(diǎn)N的other指針也要指向距離鏈表頭的第s個(gè)節(jié)點(diǎn)。這種方法的時(shí)間復(fù)雜度是O(n²)。

上面這種方法的主要缺點(diǎn)在于無法快速定位N節(jié)點(diǎn)的other所指向的S節(jié)點(diǎn)的位置，

?

下面將介紹一種時(shí)間復(fù)雜度是O(n)的方法，首先把復(fù)制的節(jié)點(diǎn)串到原節(jié)點(diǎn)后面，如下圖：

?

然后設(shè)置復(fù)制節(jié)點(diǎn)的other指針（例如 A'->other = A->other->next），如下圖

最后，把偶數(shù)順序的節(jié)點(diǎn)和奇數(shù)節(jié)點(diǎn)的指針分開。

?

// 逐個(gè)節(jié)點(diǎn)復(fù)制，并串到原節(jié)點(diǎn)后面 static void CloneNodes(ListNode *Head) {ListNode *p = Head;while (p) {ListNode *pCloned = malloc(sizeof(ListNode));pCloned->data = p->data;pCloned->next = p->next;pCloned->other = NULL;p->next = pCloned;p = pCloned->next;} }// 設(shè)置新節(jié)點(diǎn)的other指針 static void ConnectNodes(ListNode *Head) {ListNode *pCloned;ListNode *p = Head;while(p){pCloned = p->next;if (p->other) {pCloned->other = p->other->next;}p = pCloned->next;} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/chenny7/p/4113552.html

總結(jié)

以上是生活随笔為你收集整理的链表的经典问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。