一、定義

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（鏈表中每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。 相比于線性表順序結(jié)構(gòu)，操作復雜。由于不必須按順序存儲，鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間，而線性表和順序表相應的時間復雜度分別是O(logn)和O(1)。

二、經(jīng)典例題

（一）21.合并兩個有序鏈表

1.思路

根據(jù)題目描述，鏈表l1, l2是遞增的，因此容易想到使用雙指針cur1和cur2遍歷兩鏈表,根據(jù)cur1.val和cur2.val的大小關(guān)系確定節(jié)點添加順序，兩節(jié)點指針交替前進，直至遍歷完畢。
同時因為兩個鏈表都是有序的，所以，當我們遍歷完一個鏈表，剩下的那個鏈表如果沒到結(jié)尾，可以直接跟上。

2.復雜度分析

時間復雜度 O(M+N) ： M,N別為兩個鏈表的長度，合并操作需遍歷兩鏈表。
空間復雜度 O(1)： 節(jié)點引用 dum , cur使用常數(shù)大小的額外空間。

3.注意

Dummy節(jié)點的作用是作為一個虛擬的頭前節(jié)點。在不知道要返回的新鏈表的頭結(jié)點是哪一個，它可能是原鏈表的第一個節(jié)點，可能在原鏈表的中間，也可能在最后，甚至不存在（nil）。引入Dummy節(jié)點可以涵蓋所有情況，并且可以使用dummy.next返回最終需要的頭結(jié)點。

4.代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* cur1 = list1;
        ListNode* cur2 = list2;
        ListNode* dummy = new ListNode(-1); // 虛擬頭結(jié)點
        ListNode* cur = dummy;
        while (cur1 && cur2) {
        // 比較 p1 和 p2 兩個指針
        // 將值較小的的節(jié)點接到 p 指針
            if (cur1 -> val > cur2 -> val) {
                cur -> next = cur2;
                cur2 = cur2 -> next;
            }
            else {
                cur -> next = cur1;
                cur1 = cur1 -> next;
            }
            cur = cur -> next; // p 指針不斷前進
        }
        if (cur1) cur -> next = cur1;
        if (cur2) cur -> next = cur2;

        return dummy -> next;
    }
};

（二）86.分割鏈表

1.思路

具體來說，我們可以把原鏈表分成兩個小鏈表，一個鏈表中的元素大小都小于 x，另一個鏈表中的元素都大于等于 x，最后再把這兩條鏈表接到一起，就得到了題目想要的結(jié)果。

2.復雜度分析

時間復雜度 O(N)： 其中 N為鏈表長度；遍歷鏈表使用線性時間。

空間復雜度 O(1) ： 假頭節(jié)點使用常數(shù)大小的額外空間。

3.代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* dummy1 = new ListNode(-1);
        ListNode* dummy2 = new ListNode(-1);
        ListNode* small = dummy1;
        ListNode* big = dummy2;
        // 新建兩個鏈表 small,big,分別用于添加所有節(jié)點值<x、節(jié)點值>=的節(jié)點
        ListNode* cur = head;
        while (cur) {
            if (cur -> val >= x) {
                big -> next = cur;
                big = big -> next;
            }
            else {
                small -> next = cur;
                small = small -> next;
            }
            cur = cur -> next;
        }
        small -> next = dummy2 -> next; // 拼接 small 和 big
        big -> next = nullptr;
        return dummy1 -> next;
    }
};

（三）23.合并 K 個升序鏈表

1.思路

如何快速得到 k 個節(jié)點中的最小節(jié)點，接到結(jié)果鏈表上？

• 這里我們就要用到 優(yōu)先級隊列（二叉堆） 這種數(shù)據(jù)結(jié)構(gòu)，把鏈表節(jié)點放入一個最小堆，就可以每次獲得 k 個節(jié)點中的最小節(jié)點：

優(yōu)先隊列 pq 中的元素個數(shù)最多是 k，所以一次 poll 或者 add 方法的時間復雜度是 O(logk)；所有的鏈表節(jié)點都會被加入和彈出 pq，所以算法整體的時間復雜度是 O(Nlogk)，其中 k 是鏈表的條數(shù)，N 是這些鏈表的節(jié)點總數(shù)。

2.復雜度分析

時間復雜度：考慮優(yōu)先隊列中的元素不超過 k 個，那么插入和刪除的時間代價為 O(log?k)，這里最多有 kn 個點，對于每個點都被插入刪除各一次，故總的時間代價即漸進時間復雜度為 O(kn×log?k)。
空間復雜度：這里用了優(yōu)先隊列，優(yōu)先隊列中的元素不超過 k個，故漸進空間復雜度為 O(k)。

3.代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
// 時間復雜度 ： O(n ? log(k))
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return nullptr;

        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;

       priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq(
        [] (ListNode* a, ListNode* b) { return a->val > b->val; });

        for (auto head : lists) {
            if (head != nullptr) pq.push(head);
        }

        while (!pq.empty()) {
            ListNode* node = pq.top();
            pq.pop();
            p -> next = node;
            
            if (node -> next != nullptr)
                pq.push(node->next);

            p = p -> next;
        }
    return dummy -> next;
    }
};

（四）19.刪除鏈表中的倒數(shù)第N個節(jié)點

1.思路

假設(shè)鏈表有 n 個節(jié)點，倒數(shù)第 k 個節(jié)點就是正數(shù)第 n - k + 1 個節(jié)點。
是的，但是算法題一般只給你一個 ListNode 頭結(jié)點代表一條單鏈表，你不能直接得出這條鏈表的長度 n，而需要先遍歷一遍鏈表算出 n 的值，然后再遍歷鏈表計算第 n - k + 1 個節(jié)點。
也就是說，這個解法需要遍歷兩次鏈表才能得到出倒數(shù)第 k 個節(jié)點。文章來源地址http://www.zghlxwxcb.cn/news/detail-733616.html

2.復雜度分析

3.代碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
         if (head == nullptr || n == 0) return nullptr;

        ListNode* dummy = new ListNode(-1);
        dummy -> next = head;

        ListNode* x = findFromEnd(dummy, n + 1);
        x -> next = x -> next -> next;
        return dummy -> next;
    }
    ListNode* findFromEnd(ListNode* head, int k) {

    // 代碼見上文

        ListNode* slow = head;
        ListNode* fast = head;

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

到了這里，關(guān)于二、鏈表（linked-list）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！