Leetcode一刷-連結串列篇【補卡】-Day3&4/60

語言: CN / TW / HK

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指標走向。

具體實現方法:雙指標 利用precur指標,實現反轉。注意: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++寫出來的第一題,思路略有確認,但是畫圖確認的移動過程和參考解析基本一致。

這是一題經典的雙指標應用題,利用slowfast的錯位移動定位到要操作的兩個節點上。

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/

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

參考卡哥的解釋,提交的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; // 沒有閉環

}

}; ```