【資料結構】鏈表經典演算法題集錦

前言：本章將分享十一道來自LeetCode/牛客網中的經典鏈表演算法題來介紹資料結構中鏈表在演算法題中的應用，

1.洗掉鏈表元素

給你一個鏈表的頭節點 head 和一個整數 val ，請你洗掉鏈表中所有滿足 Node.val == val 的節點，并回傳 新的頭節點，OJ鏈接

思路分析：

1.遍歷找到需要洗掉的結點前一個結點,即如果cur->next->val=val,說明cur就是需要洗掉結點的前一個結點

2.讓需要洗掉結點的前一個結點與需要洗掉結點的后一個結點連接,即cur->next = cur->next->next

3.釋放需要洗掉的結點

遍歷方式：

如果 cur的下一個節點的節點值不等于給定的 val，則保留下一個節點，將 val移動到下一個節點即可，當 cur的下一個節點為空時，鏈表遍歷結束，
此程序與單鏈表的頭刪操作類似，但是單鏈表的頭刪中對一個結點和多個結點是進行分情況討論的,這就會比較麻煩,我們可以給原來鏈表增加一個啞結點，避免分類討論，

題解：

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* node=(struct ListNode*)malloc(sizeof(struct ListNode));
    node->next=head; //創建啞結點，鏈接
    struct ListNode* cur=node;//迭代 

    while(cur->next)
    {
        if(cur->next->val==val)
        {
            struct ListNode*x=cur->next;
            cur->next=cur->next->next;
            free(x);           //釋放被洗掉結點空間
        }
        else
        {
            cur=cur->next;
        }
    }
    return node->next;
}

2.反轉鏈表

給你單鏈表的頭節點 head ，請你反轉鏈表，并回傳反轉后的鏈表，OJ鏈接

思路分析：

假設鏈表為 1→2→3→?，我們想要把它改成?←1←2←3，

在遍歷鏈表時，將當前節點的 \textit{next}next 指標改為指向前一個節點，由于節點沒有參考其前一個節點，因此必須事先存盤其前一個節點，在更改參考之前，還需要存盤后一個節點，最后回傳新的頭參考，

具體步驟：

1.新建一個prev指標置為NULL，cur指向head，新建一個next，

2.進入while回圈，next保存cur下一個結點資料，同時cur指向前一個結點prev，然后prev移動到當前cur位置，cur移動到當前next位置，以此回圈

題解：

struct ListNode* reverseList(struct ListNode* head) 
{
    struct ListNode* prev = NULL;//新建一個prev指標置為NULL
    struct ListNode* cur = head;//cur指標賦值為頭結點head
    struct ListNode* next= NULL;//新建一個next
    while (cur) 
    {
        next = cur->next;//next保存下一個結點
        cur->next = prev;//cur指向前一個結點prev
        prev = cur;     //prev移動到當前cur位置
        cur = next;    //cur移動到當前next位置
    }
    return prev;
}

3.鏈表中間結點

給定一個頭結點為 head 的非空單鏈表，回傳鏈表的中間結點，

如果有兩個中間結點，則回傳第二個中間結點，OJ鏈接

思路分析（快慢指標法）：

即快指標fast比慢指標slow多走一步,這樣當快指標走完整個鏈表時候,慢指標就剛好是中間結點.其中快指標的結束條件受到結點個數的奇偶影響.

1.當結點數是偶數時候,當fast為空，即fast=NULL，slow滿足題解

2.當結點數是奇數時候,當fast為尾結點,即fast->next=NULL，slow滿足題解

題解：

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast,*slow; //定義快慢指標
    fast = slow = head;
    while(fast && (fast->next)) 
    // 當fast為空,或者fast->next為空,就結束回圈,說明此時slow已經走到了中間結點
    {
        fast = fast->next->next;//fast走兩步
        slow = slow->next; //slow走一步
    }
    return slow;
}

4.鏈表中倒數第K個結點

輸入一個鏈表，輸出該鏈表中倒數第k個節點，為了符合大多數人的習慣，本題從1開始計數，即鏈表的尾節點是倒數第1個節點，OJ鏈接

思路分析（快慢指標法）：

先讓fast走K步,然后slow與fast以相同的速度，當fast走到末尾時跳出(fast->next=NULL)，跳出后， slow 與尾節點距離為 k-1，即 slow 指向倒數第 k 個節點），

題解：

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    struct ListNode* slow,*fast;
    slow = fast = head;   //創建快慢指標
    
    while(k--)   //fast先走K步
    {
        if(fast)        //注意!!!!這里必須要判斷,為什么呢?因為題目并沒有規定k是小于等于鏈表長度的哦
            fast = fast->next;
        else
            return NULL;
    }
    while(fast)  //同步
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

5.合并兩個有序鏈表

將兩個升序鏈表合并為一個新的 升序 鏈表并回傳，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的， OJ鏈接

思路分析：

1.新建立一個新陣列，建立一個啞結點，

2.然后陣列上下兩兩比較，小的就依次放在新陣列的啞結點后，

題解：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* p1 = l1,*p2 = l2;
    struct ListNode* newhead = NULL,*tail = NULL;

    if(p1==NULL)
    {
        return p2;
    }
    if(p2==NULL)
    {
        return p1;
    }
    
    newhead = tail = (struct ListNode* )malloc(sizeof(struct ListNode));
    //創建新結點

    while(p1 && p2)  //開始一一比較并進行連接
    {
        (p1-> val) <= (p2->val) ?  //比較誰小
        (tail->next = p1,p1 = p1->next,tail = tail->next) :  
        //p1的值更小,則連接p1,然后tail和p1迭代
        (tail->next = p2,p2 = p2->next,tail = tail->next);  
        //p2的值更小,則連接p2,然后tail和p2迭代
    }
    //特別注意下這里，第一次刷犯錯了
    p1 ? (tail->next = p1):(p1);  //如果p1還有值,則把剩下的p1連接
    p2 ? (tail->next = p2):(p2);  //如果p2還有值,則把剩下的p2連接

    struct ListNode* pp = newhead->next;  //保存啞結點后面的結點
    free(newhead); //釋放啞結點
    newhead = NULL;
    return pp;
}

這里記錄下刷這道題時煩得錯誤：

真是題目做得腦子壞了，就算是代替條件判斷陳述句也是if來替代

6.鏈表分割

給你一個鏈表的頭節點 head 和一個特定值 x ，請你對鏈表進行分隔，使得所有 小于 x 的節點都出現在 大于或等于 x 的節點之前，

你不需要 保留 每個磁區中各節點的初始相對位置，OJ鏈接

思路分析：

同時創建兩個啞結點,值小于x的結點放在第一個結點后,值大于等于x的結點放在第二個結點后,等原鏈表放完后,再把第二個啞結點鏈表后面的資料連接在第一個啞結點鏈表上

題解：

struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode* small = malloc(sizeof(struct ListNode));
    struct ListNode* smallHead = small;
    struct ListNode* large = malloc(sizeof(struct ListNode));
    struct ListNode* largeHead = large;
    while (head) {
        if (head->val < x) {
            small->next = head;
            small = small->next;
        } else {
            large->next = head;
            large = large->next;
        }
        head = head->next;
    }
    large->next = NULL;
    small->next = largeHead->next;//把large啞結點后的結點鏈接給small
    return smallHead->next;//回傳small啞結點后的結點
}

7.鏈表的回文結構(第2題和第3題的綜合)

OJ鏈接

對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的演算法，判斷其是否為回文結構，給定一個鏈表的頭指標A，請回傳一個bool值，代表其是否為回文結構，保證鏈表長度小于等于900，

測驗樣例：

1->2->2->1
回傳：true

思路分析：

可以先找到中間節點，然后把后半部分逆置，最近前后兩部分一一比對，如果節點的值全部相同，則即為回文，

題解：

class PalindromeList {
public:
	bool chkPalindrome(ListNode* A) {
		if (A == NULL || A->next == NULL)
			return true;
		ListNode* slow, *fast, *prev, *cur, *nxt;
		slow = fast = A;
		//找到中間節點
		while (fast && fast->next)
		{
			slow = slow->next;
			fast = fast->next->next;
		}
		prev = NULL;
		//后半部分逆置
		cur = slow;
		while (cur)
		{
			nxt = cur->next;
			cur->next = prev;
			prev = cur;
			cur = nxt;
		}
		//逐點比對
		while (A && prev)
		{
			if (A->val != prev->val)
				return false;
			A = A->next;
			prev = prev->next;
		}
		return true;
	}
};

**怎么樣，是不是感覺就是尋找鏈表中間數和反轉鏈表兩道題的綜合，**題目難度為較難級別，但是有了前文尋找中間元素和鏈表元素逆置的基礎，這題反而更像入門級別的送分題，

8.相交鏈表

OJ鏈接

給你兩個單鏈表的頭節點 headA 和 headB ，請你找出并回傳兩個單鏈表相交的起始節點，如果兩個鏈表沒有交點，回傳 null ，

圖示兩個鏈表在節點 c1 開始相交：

題目資料 保證 整個鏈式結構中不存在環，

注意，函式回傳結果后，鏈表必須 保持其原始結構 ，

思路分析：

此題可以先計算出兩個鏈表的長度，讓長的鏈表先走相差的長度，然后兩個鏈表同時走，直到遇到相同的節點，即為第一個公共節點

題解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA=0,lenB=0;
        ListNode* curA=headA,*curB=headB;
        //計算兩個鏈表的長度
        while(curA)
        {
            lenA++;
            curA=curA->next;
        }
        while(curB)
        {
            lenB++;
            curB=curB->next;
        }
        //
        int len=abs(lenA-lenB);
        ListNode* LongList=headA,*ShortList=headB;
        if(lenA<lenB)
        {
            LongList=headB;
            ShortList=headA;
        }
        //讓長鏈表先走len步
        while(len--)
        {
            LongList=LongList->next;
        }
        //雙鏈表同時走，直到相遇
        while(LongList &&ShortList)
        {
            if(LongList==ShortList)
            return LongList;
            else
            {
                LongList=LongList->next;
                ShortList=ShortList->next;
            }
        }
        return NULL;
    }
};

9.環形鏈表I

OJ鏈接

給定一個鏈表，判斷鏈表中是否有環，

如果鏈表中有某個節點，可以通過連續跟蹤 next 指標再次到達，則鏈表中存在環， 為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）， 如果 pos 是 -1，則在該鏈表中沒有環，注意：pos 不作為引數進行傳遞，僅僅是為了標識鏈表的實際情況，

如果鏈表中存在環，則回傳 true ， 否則，回傳 false ，

進階：

你能用 O(1)（即，常量）記憶體解決此問題嗎？

思路分析：

定義快慢指標fast,slow, 如果鏈表確實有環，fast指標一定會在環內追上slow指標，

題解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode*slow,*fast;
    slow=fast=head;

    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast)
        return true;
    }
    return false;
}

10.環形鏈表II

OJ鏈接

給定一個鏈表，回傳鏈表開始入環的第一個節點， 如果鏈表無環，則回傳 null，

為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）， 如果 pos 是 -1，則在該鏈表中沒有環，注意，pos 僅僅是用于標識環的情況，并不會作為引數傳遞到函式中，

說明：不允許修改給定的鏈表，

進階：

你是否可以使用 O(1) 空間解決此題？

思路分析：

如果鏈表存在環，則fast和slow會在環內相遇，定義相遇點到入口點的距離為X,定義環的長度為C,定義頭到入口的距離為L,fast在slow進入環之后一圈內追上slow,則會得知：

slow所走的步數為:L + X

fast所走的步數為：L + X + N * C

并且fast所走的步數為slow的兩倍，故：2*(L + X) = L + X + N * C

即： L = N * C - X

所以從相遇點開始slow繼續走，讓一個指標從頭開始走，相遇點即為入口節點

比較難理解，這里畫下圖

1.套用環形鏈表I的思路，快慢指標找到相遇點

2.根據我們思路分析得出的結論：從相遇點開始slow繼續走，讓一個指標從頭開始走，相遇點即為入口節點，以此來尋找入口點，

題解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode Node;
struct ListNode *detectCycle(struct ListNode *head) {
    Node* slow,*fast;
    slow=fast=head;

    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        //標記相遇點,并重新建個指標指向頭
        if(slow==fast)
        {
            Node* meet=slow;
            Node* start=head;

            while(meet!=start)
            {
                meet=meet->next;
                start=start->next;
            }
        return meet;
        }
    }
    return NULL;
}

11.復制帶隨機指標的鏈表（這題卡了好幾次，多做做）

OJ鏈接

給你一個長度為 n 的鏈表，每個節點包含一個額外增加的隨機指標 random ，該指標可以指向鏈表中的任何節點或空節點，

構造這個鏈表的深拷貝， 深拷貝應該正好由 n 個 全新 節點組成，其中每個新節點的值都設為其對應的原節點的值，新節點的 next 指標和 random 指標也都應指向復制鏈表中的新節點，并使原鏈表和復制鏈表中的這些指標能夠表示相同的鏈表狀態，復制鏈表中的指標都不應指向原鏈表中的節點 ，

例如，如果原鏈表中有 X 和 Y 兩個節點，其中 X.random --> Y ，那么在復制鏈表中對應的兩個節點 x 和 y ，同樣有 x.random --> y ，

回傳復制鏈表的頭節點，

用一個由 n 個節點組成的鏈表來表示輸入/輸出中的鏈表，每個節點用一個 [val, random_index] 表示：

? val：一個表示 Node.val 的整數，
? random_index：隨機指標指向的節點索引（范圍從 0 到 n-1）；如果不指向任何節點，則為 null ，
你的代碼只接受原鏈表的頭節點 head 作為傳入引數，

思路分析：

1.拷貝鏈表的每一個節點，拷貝的節點先鏈接到被拷貝節點的后面

2.復制隨機指標的鏈接：拷貝節點的隨機指標指向被拷貝節點隨機指標的下一個位置

3.拆解鏈表，把拷貝的鏈表從原鏈表中拆解出來

題解：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 1.拷貝鏈表，并插入到原節點的后面
        Node* cur = head;
        while(cur)
        {
            Node* next = cur->next;
 
            Node* copy = (Node*)malloc(sizeof(Node));
            copy->val = cur->val;
 
            // 插入
            cur->next = copy;
            copy->next = next;
 
            // 迭代往下走
            cur = next;
        }
 
        // 2.置拷貝節點的random
        cur = head;
        while(cur)
        {
            Node* copy = cur->next;
            if(cur->random != NULL)
                copy->random = cur->random->next;
            else
                copy->random = NULL;
 
            cur = copy->next;
        }
 
        // 3.解拷貝節點，鏈接拷貝節點
        Node* copyHead = NULL, *copyTail = NULL;
        cur = head;
        while(cur)
        {
            Node* copy = cur->next;
            Node* next = copy->next;
 
            // copy解下來尾插
            if(copyTail == NULL)
            {
                copyHead = copyTail = copy;
            }
            else
            {   
                copyTail->next = copy;
                copyTail = copy;
            }
 
            cur->next = next;
 
            cur = next;
        }
 
        return copyHead;
    }
};

資料結構的鏈表LeetCode練習內容到此設計結束了，感謝您的閱讀！！！如果內容對你有幫助的話，記得給我三連（點贊、收藏、關注）——做個手有余香的人，