Created by potrace 1.14, written by Peter Selinger 2001-2017 Zorch's Blog

链表力扣题型总结

 
Category： DSA
  • zorchp
  • 2023年 04月23日

写在前面

其实链表的题大多数都可以用双指针(快慢指针)来做, 只不过不像数组中的双指针那样左右移动, 链表(单链表)的双指针方法都是向后移动的.

刷完链表专题, 可以总结一下链表中常用的套路: (当然, 刷题还是要到位)

  1. 不要怕浪费空间, 头(尾)结点的 dummy 最好用.
  2. 不要怕浪费指针, 多个指针的移动别搞混.
  3. 不要怕画图, 很多题画个链表模拟一下指针移动就能解出来了.

链表声明

这里是力扣通用的链表结构体声明.

需要注意不要冲突定义, 比如设计链表这道题如果在全局定义了ListNode类就会报重定义错误…

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) {}
};

基本操作

基本增删改查

707. 设计链表 - 力扣（LeetCode）;

要照顾到的点很多, 尤其是设计头插尾插时候, 其实可以直接调用现成的AddAtIndex方法, 前提是这个方法的边界条件都没问题了.

  1. 索引的有效性;
  2. 头结点的添加(通过 dummy 实现)
class MyLinkedList {
    struct Node {
        int val;
        Node* next;
        Node() : Node(0, nullptr) {}
        Node(int _val) : Node(_val, nullptr) {}
        Node(int _val, Node* _next) : val(_val), next(_next) {}
    };
    Node* head;
    size_t size;
    Node* traverse(int idx) {
        auto cur{head};
        while (idx--) cur = cur->next;
        return cur;
    }

public:
    MyLinkedList() : head(new Node), size(0) {}

    int get(int index) {
        if (index >= size || index < 0) return -1;
        return traverse(index + 1)->val;
    }

    void addAtHead(int val) { addAtIndex(0, val); }

    void addAtTail(int val) { addAtIndex(size, val); }

    void addAtIndex(int index, int val) {
        if (index > size) return;
        ++size;
        auto cur = traverse(index);
        auto tmp{new Node(val, cur->next)};
        cur->next = tmp;
    }

    void deleteAtIndex(int index) {
        if (index >= size || index < 0) return;
        --size;
        auto cur = traverse(index);
        auto tmp{cur->next};
        cur->next = cur->next->next;
        delete tmp;
    }
};

添加指定节点

剑指 Offer II 029. 排序的循环链表;

class Solution {
public:
    Node* insert(Node* head, int insertVal) {
        if (!head) { // 空节点
            head = new Node(insertVal);
            head->next = head;
            return head;
        } else if (head->next == head) { // 单节点
            head->next = new Node(insertVal, head);
            return head;
        }
        bool flg{};
        auto cur(head);
        for (; cur->next != head; cur = cur->next) {
            // 三种情况: 顺序插入, 头插入(最小值), 尾插入(最大值)
            if ((cur->val <= insertVal && cur->next->val >= insertVal) ||
                (cur->val > cur->next->val &&
                 (cur->next->val > insertVal || cur->val < insertVal))) {
                flg = true;
                auto node = new Node(insertVal, cur->next);
                cur->next = node;
                break;
            }
        }
        if (!flg) { // 遍历完后还未找到插入位置(都相同), 插在末尾
            auto node = new Node(insertVal, cur->next);
            cur->next = node;
        }
        return head;
    }
};

删除指定节点

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）;

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *dummy = new ListNode(0, head);
        auto first = dummy, second = dummy;
        while (n--) first = first->next;
        while (first && first->next) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        return dummy->next;
    }
};

83. 删除排序链表中的重复元素 - 力扣（LeetCode）;

双指针的方法: (比较复杂)

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (!head) return head;
        using lp = ListNode *;
        lp cur = head, pre{};
        bool flg{};
        while (cur) {
            while (pre && cur && cur->val == pre->val)
                cur = cur->next, flg = true;
            if (flg) pre->next = cur, flg = false;
            pre = cur;
            if (!cur) break;
            cur = cur->next;
        }
        return head;
    }
};

单指针其实就够用了:

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (!head) return head;
        ListNode *cur = head;
        while (cur->next) {
            if (cur->val == cur->next->val)
                cur->next = cur->next->next;
            else
                cur = cur->next;
        }
        return head;
    }
};

82. 删除排序链表中的重复元素 II - 力扣（LeetCode）; 双指针+哑结点

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (!head) return head;
        ListNode *dummy = new ListNode(-101, head), *cur = head, *pre = dummy;
        bool flg{};
        while (cur && cur->next) {
            while (cur->next && cur->val == cur->next->val)
                cur = cur->next, flg = true;
            if (flg)
                flg = false, pre->next = cur->next;
            else
                pre = cur; // 若此轮遍历后不是重复值, 更新pre
            cur = cur->next;
        }
        return dummy->next;
    }
};

同样, 单指针也可以做, 框架与上一题一样:

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (!head) return head;
        ListNode *dummy = new ListNode(-101, head), *cur = dummy;
        while (cur->next && cur->next->next) {
            if (cur->next->val == cur->next->next->val) {
                int x = cur->next->val;
                while (cur->next && cur->next->val == x)
                    cur->next = cur->next->next;
            } else
                cur = cur->next;
        }
        return dummy->next;
    }
};

1171. 从链表中删去总和值为零的连续节点;(这个题的处理过程很像 LRU 缓存, 需要哈希记录前缀和)

一个问题就是, 如果释放了被删除的节点内存, 则会报错heap-use-after-free, 很奇怪, 本地测试没问题

class Solution {
public:
    ListNode *removeZeroSumSublists(ListNode *head) {
        auto dum = new ListNode(0, head), cur = dum;
        unordered_map<int, ListNode *> dic;
        int sum{};
        while (cur) {
            sum += cur->val;
            dic[sum] = cur;
            cur = cur->next;
        }
        sum = 0;
        cur = dum;
        while (cur) {
            sum += cur->val;
            auto tmp = dic[sum]->next, pre{cur->next};
            // while (pre != tmp) {
            //     auto t=pre->next;
            //     delete pre;
            //     pre = t;
            // }
            cur->next = tmp;
            cur = cur->next;
        }
        return dum->next;
    }
};

反转

206. 反转链表 - 力扣（LeetCode）;剑指 Offer II 024. 反转链表 - 力扣（LeetCode）; 迭代法: (常见)

class Solution {
public:
    ListNode *reverseList(ListNode *head) {
        ListNode *cur = head, *pre = nullptr;
        while (cur) {
            auto tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

递归写法: (可能会问)

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* ans = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return ans;
    }
};

反转打印

剑指 Offer 06. 从尾到头打印链表;

// 没什么技术含量的写法
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if (!head) return {};
        auto cur(head);
        vector<int> ans{};
        while (cur) {
            ans.emplace_back(cur->val);
            cur = cur->next;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
// 递归写法
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if (!head) return {};
        auto cur(head);
        vector<int> ans{};
        function<void(ListNode*)> f = [&](ListNode* node) {
            if (!node) return;
            f(node->next);
            ans.emplace_back(node->val);
        };
        f(head);
        return ans;
    }
};
// 栈模拟
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if (!head) return {};
        auto cur(head);
        vector<int> ans{};
        stack<ListNode*> st;
        for (auto cur(head); cur; cur = cur->next) st.emplace(cur);
        for (; !st.empty(); st.pop()) ans.emplace_back(st.top()->val);
        return ans;
    }
};

旋转

61. 旋转链表 - 力扣（LeetCode）;

// 直接模拟: 速度慢
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (k == 0 || !head) return head;
        ListNode *mid{head}, *cur{head};
        int len{};
        while (cur && cur->next) ++len, cur = cur->next;
        ++len;
        k %= len;
        if (k == 0) return head;
        int m = len - k;
        while (--m) mid = mid->next;
        ListNode* new_head = mid->next;
        mid->next = nullptr;
        cur->next = head;
        return new_head;
    }
};

// 闭合为环: 经典思路, 用到了取余性质, 事实就是运行时间的区别不大
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || k == 0) return head;
        auto cur{head};
        int n{1};
        while (cur->next) cur = cur->next, ++n;
        k %= n;
        if (k == 0) return head;
        cur->next = head; // 连接成环
        k = n - k;
        while (--k) head = head->next; // 找断开的点
        auto ans{head->next};
        head->next = nullptr;
        return ans;
    }
};

找中间节点

876. 链表的中间结点 - 力扣（LeetCode）;

快慢指针, 根据速度的不同分出来中间节点, 一次遍历即可.

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if (!head || !head->next) return head;
        auto fa = head, lo = head;
        while (fa && fa->next) lo = lo->next, fa = fa->next->next;
        return lo;
    }
};

合并

1669. 合并两个链表 - 力扣（LeetCode）;

class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        auto l = list1;
        int c = b - a + 2;
        while (--a) l = l->next;
        auto r = l;
        while (c--) r = r->next;
        l->next = list2;
        auto cur = list2;
        while (cur->next) cur = cur->next;
        cur->next = r;
        return list1;
    }
};

21. 合并两个有序链表 - 力扣（LeetCode）;剑指 Offer 25. 合并两个排序的链表 - 力扣（LeetCode）;

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        auto node = new ListNode, cur = node;
        while (list1 && list2) {
            if (list1->val < list2->val)
                cur->next = list1, list1 = list1->next;
            else
                cur->next = list2, list2 = list2->next;
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2;
        return node->next;
    }
};

分隔

86. 分隔链表 - 力扣（LeetCode）;(类似合并排序链表, 可以用来做链表上的快排)

// 不使用额外空间的方法
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        auto large = new ListNode, small = new ListNode;
        auto cur1{large}, cur2{small};
        while (head) {
            if (head->val >= x)
                cur1->next = head, cur1 = cur1->next;
            else
                cur2->next = head, cur2 = cur2->next;
            head = head->next;
        }
        cur1->next = nullptr;     // 断大的尾结点
        cur2->next = large->next; // 小的尾结点指向大的头的next
        auto ans = small->next;
        delete small;
        delete large;
        return ans;
    }
};

复制

138. 复制带随机指针的链表;剑指 Offer 35. 复杂链表的复制;

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return head;
        // 连接复制出来的节点
        for (auto cur(head); cur; cur = cur->next->next) {
            auto tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
        }
        // 添加上 random 节点
        for (auto cur(head); cur; cur = cur->next->next)
            cur->next->random = cur->random ? cur->random->next : nullptr;
        // 拆分节点
        auto ans = head->next;
        for (auto cur(head); cur; cur = cur->next) {
            auto tmp(cur->next);
            cur->next = cur->next->next;
            tmp->next = tmp->next ? tmp->next->next : nullptr;
        }
        return ans;
    }
};

重排

143. 重排链表 - 力扣（LeetCode）;

class Solution {
public:
    void reorderList(ListNode* head) {
        vector<ListNode*> arr;
        for (auto cur(head); cur; cur = cur->next) arr.emplace_back(cur);
        int n = arr.size();
        auto cur(head);
        for (int r{n - 1}; r > n / 2; --r) {
            auto tmp = arr[r];
            tmp->next = cur->next;
            cur->next = tmp;
            cur = cur->next->next;
        }
        if (n & 1)
            cur->next = nullptr;
        else
            cur->next->next = nullptr;
    }
};

不要额外空间的方法:

环形链表

141. 环形链表 - 力扣（LeetCode）;

class Solution {
public:
    bool hasCycle(ListNode *head) {
        auto f = head, l = head;
        while (1) {
            if (!f || !f->next) return false;
            f = f->next->next;
            l = l->next;
            if (f == l) return true;
        }
    }
};

$\bigstar$142. 环形链表 II;剑指 Offer II 022. 链表中环的入口节点;(经典算法, 需要找一个等价关系)

从相遇点到入环点的距离($c$)+$(n-1)$环周长等于头结点到入环点的长度.

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head) return head;
        auto f = head, s = head;
        while (f) {
            s = s->next;
            if (!f->next) return nullptr; // 无环
            f = f->next->next;
            if (f == s) {
                auto ptr = head;
                while (ptr != s) ptr = ptr->next, s = s->next;
                return ptr;
            }
        }
        return nullptr;
    }
};

综合(进阶)题目

排序

单向链表排序最快的算法是归并, 双向链表排序最快的算法是快速排序.

147. 对链表进行插入排序;

148. 排序链表; (这个是单链表上排序的最优解法: 归并排序)

相当于两个题的组合:

当然还有快排: (太复杂了, 直接拿来主义, 过这道题会超时)

QuickSort on Singly Linked List;

数字链表相加

2. 两数相加 - 力扣（Leetcode）;

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dum = new ListNode(0), *cur = dum;
        int carry{}, num{};
        while (l1 || l2 || carry) {
            int n1{}, n2{};
            if (l1)
                n1 = l1->val, l1 = l1->next;
            if (l2)
                n2 = l2->val, l2 = l2->next;
            num = n1 + n2 + carry;
            cur->next = new ListNode(num % 10);
            cur = cur->next;
            carry = num / 10;
        }
        return dum->next;
    }
};

445. 两数相加 II - 力扣（Leetcode）;

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        auto reverse = [](ListNode* l) {
            ListNode *cur = l, *pre = nullptr;
            while (cur) {
                auto tmp = cur->next;
                cur->next = pre;
                pre = cur;
                cur = tmp;
            }
            return pre;
        };
        l1 = reverse(l1);
        l2 = reverse(l2);
        auto dum = new ListNode;
        for (int n1, n2, num, carry{}; l1 || l2 || carry;) {
            n1 = n2 = 0;
            if (l1)
                n1 = l1->val, l1 = l1->next;
            if (l2)
                n2 = l2->val, l2 = l2->next;
            num = n1 + n2 + carry;
            auto tmp = new ListNode(num % 10, dum->next);
            dum->next = tmp;
            carry = num / 10;
        }
        return dum->next;
    }
};

更好的方法, 不需要翻转:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int, list<int>> s1, s2; // list in container
        for (; l1; l1 = l1->next)
            s1.emplace(l1->val);
        for (; l2; l2 = l2->next)
            s2.emplace(l2->val);
        auto dum = new ListNode;
        for (int n1, n2, num, carry{}; !s1.empty() || !s2.empty() || carry;) {
            n1 = n2 = 0;
            if (!s1.empty())
                n1 = s1.top(), s1.pop();
            if (!s2.empty())
                n2 = s2.top(), s2.pop();
            num = n1 + n2 + carry;
            dum->next = new ListNode(num % 10, dum->next);
            carry = num / 10;
        }
        return dum->next;
    }
};

回文链表

234. 回文链表 - 力扣（LeetCode）;剑指 Offer II 027. 回文链表 - 力扣（LeetCode）;面试题 02.06. 回文链表 - 力扣（LeetCode）;

直接存数组模拟可以做, $O(1)$空间有一定难度, 下面主要说$O(1)$做法, 综合了上述的很多基本操作.

  • 找到中节点(奇数长度是中节点, 偶数长度是中间靠右的结点)
  • 翻转中节点开始往后的后部分链表
  • 对比两个部分, 判断回文情况
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        auto mid = find_mid(head), nhead = reverse(mid);
        while (nhead) {
            if (head->val != nhead->val) return false;
            head = head->next;
            nhead = nhead->next;
        }
        return true;
    }
    ListNode* reverse(ListNode* head) {
        ListNode *cur = head, *pre = nullptr;
        while (cur) {
            auto tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    ListNode* find_mid(ListNode* head) {
        ListNode *fast = head, *low = head, *tmp{};
        while (fast && fast->next) {
            fast = fast->next->next;
            low = low->next;
        }
        return low;
    }
};

合并排序链表

23. 合并K个升序链表 - 力扣（LeetCode）;(分治, 或者优先队列, 优先队列方便)

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return {};
        auto cmp = [](const auto& lhs, const auto& rhs) {
            return lhs->val > rhs->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        // int k = lists.size();
        auto dum = new ListNode, cur = dum;
        for (auto node : lists)
            if (node) 
                pq.emplace(node);

        for (; !pq.empty(); pq.pop(), cur = cur->next) {
            auto tmp = pq.top();
            if (tmp) 
                cur->next = tmp;
            if (tmp->next) 
                pq.emplace(tmp->next);
        }
        return dum->next;
    }
};

反转链表

指定区间

92. 反转链表 II - 力扣（LeetCode）;(用到三个指针的穿针引线法, 画个图就出来了)

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        auto dummy = new ListNode(0, head), pre = dummy;
        for (int i{}; i < left - 1; ++i) pre = pre->next; // 左端指针
        auto cur = pre->next, post = cur;
        int cnt = right - left;
        for (int i{}; i < cnt; ++i) post = post->next;
        while (cnt--) {
            pre->next = cur->next;
            auto tmp = post->next;
            post->next = cur;
            cur->next = tmp;
            cur = pre->next;
        }
        auto ans = dummy->next;
        delete dummy;
        return ans;
    }
};

指定组

25. K 个一组翻转链表 - 力扣（LeetCode）;

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int n{};
        for (auto cur{head}; cur; cur = cur->next) ++n;
        auto dum = new ListNode(0, head), pp = dum, cur = head;
        ListNode* pre{};
        for (; n >= k; n -= k) {
            for (int i{}; i < k; ++i) { // reverse
                auto tmp = cur->next;
                cur->next = pre;
                pre = cur;
                cur = tmp;
            }
            // link
            auto x = pp->next;
            pp->next->next = cur;
            pp->next = pre;
            pp = x;
        }
        return dum->next;
    }
};
search search_off backspace