theme: juejin highlight: github

鏈表全攻略

第一次接觸鏈表的算法題，個人的整體感受是：多多畫圖，模擬指針的走法，弄清楚指針的先後移動順序，明確指針的起始/終止位置和while跳出的終止條件。由於鏈表總是順序移動的，所以while語句會經常遇到，特別是在尋找長度時。

在這裏實現了用c++實現算法不報錯的第一步，並嘗試利用日誌輸出c++代碼的中間過程來尋找代碼問題。

本篇blog將對day3&4打卡的全部內容進行梳理。文章圖來源於卡哥的代碼隨想錄。

鏈表理論基礎

鏈表掃盲

鏈表是一種通過指針串聯在一起的線性結構，每個節點有兩個部分組成，一個是數據域一個是指針域(存放指向下一個節點的指針)，最後一個節點的指針域指向NULL（空指針）。

鏈表的頭節點head是進入鏈接的入口節點。

鏈表定義圖

上圖描述的即為單鏈表，該類鏈表每個節點只有一個指向的指針。 c++實現的單鏈表結構體： c++ // 單鏈表 struct ListNode{ int val; // 節點上存儲的元素 ListNode *next; // 指向下一個節點的指針 ListNode(int x) : val(x), next(NULL) {} // 節點的構造函數 }; // 最後面的這個分號不要忘記 其實c++會默認生成一個構造函數，但是這個構造函數會無法直接在初始化的時候給變量賦值。 ```c++ // 使用自己寫的構造函數，初始化節點 ListNode* head = new ListNode(5); // 一個新的鏈表需要新開闢一個內存空間

// 使用默認的構造函數，初始化節點； ListNode* head = new ListNode(); head->val = 5; ```

此處，補充python的鏈表類： python class ListNode: def __init__(self, val, next=None): self.val = val self.next = next

鏈表和數組的不同之處，除了具有指針域之外，內存分佈也不是連續的，而是散亂分佈在內存中的某地址上，分配機制取決於操作系統的內存管理。

鏈表節點在內存中的分配圖

鏈表操作

刪除節點 1. 將指向被刪除節點的next指針指向下一個節點； 2. 若使用c++，則需要手動釋放被刪除節點的內存。 ListNode * tmp = C->next; delete tmp;

刪除節點步驟

添加節點 鏈表的添加和刪除都是O(1)操作，不會影響到其他節點，但是需要花O(n)的時間複雜度，搜索指定位置的節點，因為節點總是從頭開始查找的，利用next指針進行刪除操作。

添加節點步驟

與數組的比較

|| 插入/刪除（時間複雜度） | 查詢（時間複雜度）|適用場景| |--------------| ------ | ----- | --------| |數組|O(n)|O(1)|數據量固定，頻繁查詢，較少增刪| |鏈表|O(1)|O(n)|數據量不固定，頻繁增刪，較少查詢|

其他鏈表類型

雙鏈表

支持向前向後查詢，除了next之外，還有prev指針。

雙鏈表

循環鏈表

首尾相連的鏈表

循環鏈表

Leetcode相關題目及解法要義

203. 移除鏈表元素

題目鏈接： https://leetcode.cn/problems/remove-linked-list-elements/

此題是虛擬頭節點的入門題，虛擬頭節點的使用一般是為了避免鏈表對頭節點的單獨處理。最後返回的頭節點是return dummyHead->next;

虛擬頭節點的入門題

c++使用虛擬頭節點的思路：

c++ class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead = new ListNode(0); // 設置一個虛擬頭結點 dummyHead->next = head; // 將虛擬頭結點指向head，這樣方面後面做刪除操作 ListNode* cur = dummyHead; while (cur->next != NULL) { if(cur->next->val == val) { ListNode* tmp = cur->next; cur->next = cur->next->next; delete tmp; } else { cur = cur->next; } } head = dummyHead->next; delete dummyHead; return head; } }; python使用虛擬頭節點的思路（可以不用手動釋放刪除的節點內存）： ```python

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: dummy_head = ListNode(next=head) #添加一個虛擬節點 cur = dummy_head while(cur.next!=None): if(cur.next.val == val): cur.next = cur.next.next #刪除cur.next節點 else: cur = cur.next return dummy_head.next ```

707. 設計鏈表

題目鏈接：https://leetcode.cn/problems/design-linked-list/

此題共涉及了鏈表的五個接口 - 獲取鏈表第index個節點的數值； - 在鏈表的最前面插入一個節點； - 在鏈表的最後面插入一個節點； - 在鏈表第index個節點前面插入一個節點； - 刪除鏈表的第index個節點。

本題在初始化鏈表時需要加一個_size變量來記錄鏈表的長度，同時，利用虛擬頭節點ListNode *dummyHead = new ListNode(0)代替真正的頭節點。

c++實現的單鏈表操作代碼： ```c++ class MyLinkedList { public: // 定義鏈表節點結構體 struct LinkedNode { int val; LinkedNode* next; LinkedNode(int val):val(val), next(nullptr){} };

// 初始化鏈表
MyLinkedList() {
    _dummyHead = new LinkedNode(0); // 這裏定義的頭結點 是一個虛擬頭結點，而不是真正的鏈表頭結點
    _size = 0;
}

// 獲取到第index個節點數值，如果index是非法數值直接返回-1， 注意index是從0開始的，第0個節點就是頭結點
int get(int index) {
    if (index > (_size - 1) || index < 0) {
        return -1;
    }
    LinkedNode* cur = _dummyHead->next;
    while(index--){ // 如果--index 就會陷入死循環
        cur = cur->next;
    }
    return cur->val;
}

// 在鏈表最前面插入一個節點，插入完成後，新插入的節點為鏈表的新的頭結點
void addAtHead(int val) {
    LinkedNode* newNode = new LinkedNode(val);
    newNode->next = _dummyHead->next;
    _dummyHead->next = newNode;
    _size++;
}

// 在鏈表最後面添加一個節點
void addAtTail(int val) {
    LinkedNode* newNode = new LinkedNode(val);
    LinkedNode* cur = _dummyHead;
    while(cur->next != nullptr){
        cur = cur->next;
    }
    cur->next = newNode;
    _size++;
}

// 在第index個節點之前插入一個新節點，例如index為0，那麼新插入的節點為鏈表的新頭節點。
// 如果index 等於鏈表的長度，則説明是新插入的節點為鏈表的尾結點
// 如果index大於鏈表的長度，則返回空
// 如果index小於0，則置為0，作為鏈表的新頭節點。
void addAtIndex(int index, int val) {
    if (index > _size || index < 0) {
        return;
    }
    LinkedNode* newNode = new LinkedNode(val);
    LinkedNode* cur = _dummyHead;
    while(index--) {
        cur = cur->next;
    }
    newNode->next = cur->next;
    cur->next = newNode;
    _size++;
}

// 刪除第index個節點，如果index 大於等於鏈表的長度，直接return，注意index是從0開始的
void deleteAtIndex(int index) {
    if (index >= _size || index < 0) {
        return;
    }
    LinkedNode* cur = _dummyHead;
    while(index--) {
        cur = cur ->next;
    }
    LinkedNode* tmp = cur->next;
    cur->next = cur->next->next;
    delete tmp;
    _size--;
}

// 打印鏈表
void printLinkedList() {
    LinkedNode* cur = _dummyHead;
    while (cur->next != nullptr) {
        cout << cur->next->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

private: int _size; LinkedNode* _dummyHead; python實現的雙鏈表代碼：python

雙鏈表

相對於單鏈表, Node新增了prev屬性

class Node:

def __init__(self, val):
    self.val = val
    self.prev = None
    self.next = None

class MyLinkedList:

def __init__(self):
    self._head, self._tail = Node(0), Node(0)  # 虛擬節點
    self._head.next, self._tail.prev = self._tail, self._head
    self._count = 0  # 添加的節點數

def _get_node(self, index: int) -> Node:
    # 當index小於_count//2時, 使用_head查找更快, 反之_tail更快
    if index >= self._count // 2:
        # 使用prev往前找
        node = self._tail
        for _ in range(self._count - index):
            node = node.prev
    else:
        # 使用next往後找
        node = self._head   
        for _ in range(index + 1):
            node = node.next
    return node

def get(self, index: int) -> int:
    """
    Get the value of the index-th node in the linked list. If the index is invalid, return -1.
    """
    if 0 <= index < self._count:
        node = self._get_node(index)
        return node.val
    else:
        return -1

def addAtHead(self, val: int) -> None:
    """
    Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
    """
    self._update(self._head, self._head.next, val)

def addAtTail(self, val: int) -> None:
    """
    Append a node of value val to the last element of the linked list.
    """
    self._update(self._tail.prev, self._tail, val)

def addAtIndex(self, index: int, val: int) -> None:
    """
    Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
    """
    if index < 0:
        index = 0
    elif index > self._count:
        return
    node = self._get_node(index)
    self._update(node.prev, node, val)

def _update(self, prev: Node, next: Node, val: int) -> None:
    """
        更新節點
        :param prev: 相對於更新的前一個節點
        :param next: 相對於更新的後一個節點
        :param val:  要添加的節點值
    """
    # 計數累加
    self._count += 1
    node = Node(val)
    prev.next, next.prev = node, node
    node.prev, node.next = prev, next

def deleteAtIndex(self, index: int) -> None:
    """
    Delete the index-th node in the linked list, if the index is valid.
    """
    if 0 <= index < self._count:
        node = self._get_node(index)
        # 計數-1
        self._count -= 1
        node.prev.next, node.next.prev = node.next, node.prev

```

206. 反轉鏈表

題目鏈接：https://leetcode.cn/problems/reverse-linked-list/

本題的關鍵在於不開闢新的內存空間，實現反轉。即，每次指針滑動對應修改節點的next指針走向。

具體實現方法：雙指針 利用pre和cur指針，實現反轉。注意：pred指向的是虛擬頭節點，這是因為頭節點反轉之後，->next = nullptr，利用while實現，終止條件為cur == nullptr。

c++實現的雙指針代碼為： c++ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* temp; // 保存cur的下一個節點 ListNode* cur = head; ListNode* pre = NULL; while(cur) { temp = cur->next; // 保存一下 cur的下一個節點，因為接下來要改變cur->next cur->next = pre; // 翻轉操作 // 更新pre 和 cur指針 pre = cur; cur = temp; } return pre; } };

此題，可以用遞歸法改寫內部的while語句。 ```c++ class Solution { public: ListNode reverse(ListNode pre,ListNode cur){ if(cur == NULL) return pre; ListNode temp = cur->next; cur->next = pre; // 可以和雙指針法的代碼進行對比，如下遞歸的寫法，其實就是做了這兩步 // pre = cur; // cur = temp; return reverse(cur,temp); } ListNode reverseList(ListNode head) { // 和雙指針法初始化是一樣的邏輯 // ListNode cur = head; // ListNode pre = NULL; return reverse(NULL, head); }

}; python實現的代碼：python

雙指針

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

class Solution: def reverseList(self, head: ListNode) -> ListNode: cur = head
pre = None while(cur!=None): temp = cur.next # 保存一下 cur的下一個節點，因為接下來要改變cur->next cur.next = pre #反轉 #更新pre、cur指針 pre = cur cur = temp return pre

遞歸法

class Solution: def reverseList(self, head: ListNode) -> ListNode:

    def reverse(pre,cur):
        if not cur:
            return pre

        tmp = cur.next
        cur.next = pre

        return reverse(cur,tmp)

    return reverse(None,head)

```

24. 兩兩交換鏈表中的節點

題目鏈接：https://leetcode.cn/problems/swap-nodes-in-pairs/

第一次做的時候用的是python，一開始寫的比較複雜，後來看了參考代碼，用了3個節點: pre,cur,post分別代表前中後三個節點位置。但本題用c++寫會比用python寫邏輯更清楚一些。

python參考代碼： ```python

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

class Solution: def swapPairs(self, head: ListNode) -> ListNode: res = ListNode(next=head) pre = res

    # 必須有pre的下一個和下下個才能交換，否則説明已經交換結束了
    while pre.next and pre.next.next:
        cur = pre.next
        post = pre.next.next

        # pre，cur，post對應最左，中間的，最右邊的節點
        cur.next = post.next
        post.next = cur
        pre.next = post

        pre = pre.next.next
    return res.next

```

c++參考代碼： ```c++ class Solution { public: ListNode swapPairs(ListNode head) { ListNode dummyHead = new ListNode(0); // 設置一個虛擬頭結點 dummyHead->next = head; // 將虛擬頭結點指向head，這樣方面後面做刪除操作 ListNode cur = dummyHead; while(cur->next != nullptr && cur->next->next != nullptr) { ListNode tmp = cur->next; // 記錄臨時節點 ListNode tmp1 = cur->next->next->next; // 記錄臨時節點

        cur->next = cur->next->next;    // 步驟一
        cur->next->next = tmp;          // 步驟二
        cur->next->next->next = tmp1;   // 步驟三

        cur = cur->next->next; // cur移動兩位，準備下一輪交換
    }
    return dummyHead->next;
}

}; ```

19. 刪除鏈表的倒數第N個節點

題目鏈接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

這道題是獨立用c++寫出來的第一題，思路略有確認，但是畫圖確認的移動過程和參考解析基本一致。

這是一題經典的雙指針應用題，利用slow和fast的錯位移動定位到要操作的兩個節點上。

c++參考代碼： c++ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* slow = dummyHead; ListNode* fast = dummyHead; while(n-- && fast != NULL) { fast = fast->next; } fast = fast->next; // fast再提前走一步，因為需要讓slow指向刪除節點的上一個節點 while (fast != NULL) { fast = fast->next; slow = slow->next; } slow->next = slow->next->next; return dummyHead->next; } };

面試題02.07 鏈表相交

題目鏈接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

這道題的解題關鍵在於：先找到兩個鏈表的長度差，然後再同步移動。 c++ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode* curA = headA; ListNode* curB = headB; int lenA = 0, lenB = 0; while (curA != NULL) { // 求鏈表A的長度 lenA++; curA = curA->next; } while (curB != NULL) { // 求鏈表B的長度 lenB++; curB = curB->next; } curA = headA; curB = headB; // 讓curA為最長鏈表的頭，lenA為其長度 if (lenB > lenA) { swap (lenA, lenB); swap (curA, curB); } // 求長度差 int gap = lenA - lenB; // 讓curA和curB在同一起點上（末尾位置對齊） while (gap--) { curA = curA->next; } // 遍歷curA 和 curB，遇到相同則直接返回 while (curA != NULL) { if (curA == curB) { return curA; } curA = curA->next; curB = curB->next; } return NULL; } }; + 時間複雜度: O(m+n) + 空間複雜度: O(1)

142. 環形鏈表II

題目鏈接：https://leetcode.cn/problems/linked-list-cycle-ii/

🌟🌟🌟此題難度較高，採用的方法是：快慢指針法，分別定義fast和slow指針，從頭結點出發，fast指針每次移動兩個節點，slow指針每次移動一個節點，如果fast和slow指針在途中相遇，説明這個鏈表有環。然而確定兩者入環的節點需要一些數學推導，可以參考卡哥的詳細推導，需要多看幾遍。

參考卡哥的解釋，提交的c++代碼如下，本題需要在while循環中在滿足條件的情況下return。 ``` c++ class Solution { public: ListNode detectCycle(ListNode head) { // 難題，第一次做，需要用到一些推導 // 此處的快慢指針是快指針每次移動2個節點，慢指針每次移動1個節點； // 這個題目在推導過程中用的等式是不能用虛擬頭指針做的；如果用了虛擬頭指針，公式就不成立了； // 所以對只有一個節點的問題，需要單獨討論

    ListNode* slow;
    ListNode* quick;
    // cout << head << endl;
    quick = head;
    slow = head;

    // 這個題目 我出錯的原因在於不會在while中return 
    while (quick != NULL && quick->next != NULL){ // 還有一個可能是quick->next是NULL
        quick = quick->next->next; //快指針每次走兩個節點
        slow = slow->next; // 慢指針每次走一個節點

        if (quick == slow){ //也就是當兩者相遇時
        // 根據畫圖後的公式推導，在相遇點生成一個index1，並從head開始走一個index2,兩個指針每次都只走一步，直到兩者相遇;
        // x = (n-1)(y+z)+z
            ListNode* index1 = quick; 
            ListNode* index2 = head;

            while (index1 != index2){
                index1 = index1->next;
                index2 = index2->next;
                cout << index1->val << " " << index2->val << endl;
    }
        return index1; // 若index1 和index2指針相遇，當前節點就是環的入口
        }

    } // 只要快指針不會到達NULL指針，這就説明有個閉環，否則，就直接返回NULL

    return NULL; // 沒有閉環

}

}; ```

Leetcode一刷-鏈表篇【補卡】-Day3&4/60

鏈表全攻略

鏈表理論基礎

鏈表掃盲

鏈表操作

與數組的比較

其他鏈表類型

Leetcode相關題目及解法要義

203. 移除鏈表元素

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

707. 設計鏈表

雙鏈表

相對於單鏈表, Node新增了prev屬性

206. 反轉鏈表

雙指針

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

遞歸法

24. 兩兩交換鏈表中的節點

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

19. 刪除鏈表的倒數第N個節點

面試題02.07 鏈表相交

142. 環形鏈表II