链表

写在前面

上大学以前没有学习过任何编程相关的内容，甚至电脑也仅限于上个网课。大一上学期的C语言程序设计的机考让我深受打击。后来刷了一些力扣的题目，自以为大有长进。但是对算法和数据结构的学习一直不是很系统，所以现在想照着labuladong的刷题笔记好好学一学。tag的名字是变强，算是致敬我最喜欢的apex选手青野了吧。

LeetCode21 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

解析：

比较简单。

解答：

/**
 * 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 *dummy = new ListNode(-1);
    ListNode *p = dummy;
    while(list1 != nullptr && list2 != nullptr){
        if (list1->val <= list2->val){
            p->next = list1;
            list1 = list1->next;
        }else{
            p->next = list2;
            list2 = list2->next;
        }
        p = p->next;
    }
    if (list1 != nullptr){
        p->next = list1;
        list1 = list1->next;
        p = p->next;
    }
    if(list2 != nullptr){
        p->next = list2;
        list2 = list2->next;
        p = p->next;
    }
    return dummy->next;
}
};

LeetCode141 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104] -105 <= Node.val <= 105 pos 为 -1 或者链表中的一个有效索引。

解析：

环形链表这种问题，可以通过快慢指针的方法解决，形象地说就是龟兔赛跑，只不过兔子这把勤奋了，不开摆了。这里我们一般可以快指针步长为2，慢指针步长为1。若能追上慢指针，则说明该链表中必定存在回路。

解答：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
   bool hasCycle(ListNode *head){
    if (head == nullptr || head->next == nullptr)return false;
    ListNode *slow = head, *fast = head;
    while(fast != nullptr && fast->next != nullptr){
        fast = fast->next->next;
        slow = slow->next;
        if (slow == fast)return true;
    }
    return false;
}
};

补充：

如何计算这个环的起点？

ListNode detectCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    // 上面的代码类似 hasCycle 函数
    if (fast == null || fast.next == null) {
        // fast 遇到空指针说明没有环
        return null;
    }

    // 重新指向头结点
    slow = head;
    // 快慢指针同步前进，相交点就是环起点
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

可以看到，当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

为什么要这样呢？这里简单说一下其中的原理。

我们假设快慢指针相遇时，慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步：

fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。

假设相遇点距环的起点的距离为 m，那么结合上图的 slow 指针，环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。

巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。因为结合上图的 fast 指针，从相遇点开始走k步可以转回到相遇点，那走 k - m 步肯定就走到环起点了：

所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后一定会相遇，相遇之处就是环的起点了。

LeetCode19 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

解析：

最朴素的想法是遍历，并且这个的时间复杂度也不高，也就是空间复杂度略微高一丁点。

这道题目数据结构课上也讲过，双指针的思想，也算是一前一后两个指针吧。快点的指针先走n步，然后慢的指针再走，这样子它们中间的距离就是n。注意为了防止删除的就是头节点的情况，我们需要声明一个哑节点，以帮助我们更好的定位操作之后的头节点。于是乎这边的距离就是n + 1，正好可以找到删除的节点的前一个结点。完美！

解答：

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) {
        ListNode *dummy = new ListNode(0, head);
        ListNode *fast = head;
        ListNode *slow = dummy;
        for (int i = 0; i < n; ++i) {
            fast = fast->next;
        }
        while (fast != nullptr){
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        ListNode *ans = dummy->next;
        delete dummy;
        return ans;
    }
};

不过再评论区看到了一个很骚的递归，不得不佩服。。。

class Solution {
public:
    int cur=0;
    ListNode* removeNthFromEnd(ListNode* head, int n) {
       if(!head) return NULL;
       head->next = removeNthFromEnd(head->next,n);
       cur++;
       if(n==cur) return head->next;
       return head;
    }
};

LeetCode86 分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

提示：
- 链表中节点的数目在范围 [0, 200] 内
- -100 <= Node.val <= 100
- -200 <= x <= 200

解析：

相当于合并链表的逆过程，注意我们只需要分成小于和大于等于这两个子链表，因此我们不需要在意子链表中的大小顺序。注意哑节点的使用。

解答：

ListNode* partition(ListNode* head, int x) {
    ListNode *dummy1 = new ListNode(-1);
    ListNode *dummy2 = new ListNode(-1);
    ListNode *p1 = dummy1, *p2 = dummy2, *p = head;
    while (p != nullptr){
        if (p->val < x){
            p1->next = p;
            p1 = p1->next;
        }else{
            p2->next = p;
            p2 = p2->next;
        }
        ListNode *temp = p->next;
        p->next = nullptr;
        p = temp;
    }
    p1->next = dummy2->next;
    return dummy1->next;
}

LeetCode23 合并k个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

顺序合并

最朴素的想法就是用到之前的21题。加上这题的时间复杂度要求是很低的，可以大胆地先ac掉。

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy;
        while(list1 != nullptr && list2 != nullptr){
            if (list1->val <= list2->val){
                p->next = list1;
                list1 = list1->next;
            }else{
                p->next = list2;
                list2 = list2->next;
            }
            p = p->next;
        }
        if (list1 != nullptr){
            p->next = list1;
            list1 = list1->next;
            p = p->next;
        }
        if(list2 != nullptr){
            p->next = list2;
            list2 = list2->next;
            p = p->next;
        }
        return dummy->next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *p = nullptr;
        for (int i = 0; i < lists.size(); ++i) {
            p = mergeTwoLists(p, lists[i]);
        }
        return p;
    }

分治

顺序合并我们是两个两个地处理，我们很容易就想到能否同时间处理多个组合。这就用到了分而治之的思想。

class Solution {
public:
     ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *dummy = new ListNode(-1);
        ListNode *p = dummy;
        while(list1 != nullptr && list2 != nullptr){
            if (list1->val <= list2->val){
                p->next = list1;
                list1 = list1->next;
            }else{
                p->next = list2;
                list2 = list2->next;
            }
            p = p->next;
        }
        if (list1 != nullptr){
            p->next = list1;
            list1 = list1->next;
            p = p->next;
        }
        if(list2 != nullptr){
            p->next = list2;
            list2 = list2->next;
            p = p->next;
        }
        return dummy->next;
    }

    ListNode* merge(vector<ListNode*> &lists, int l, int r){
        if (l == r)return lists[l];
        if (l > r)return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

Eureka!

优先级队列

这个是看题解和labuladong才知道了优先级队列（二叉堆）这个东西，相关的内容直接上链接吧（引个流）。思路就是我们通过优先级队列每次找到最小的节点（也就是二叉树的头节点），然后取出来删除掉，再插入新的进行新一轮树的生成，在时间复杂度上面其实差不多，但是空间复杂度从分治的\[O(logn)\]变成了\[O(n)\]。

二叉堆详解实现优先级队列 :: labuladong的算法小抄

class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};

labuladong的java版本

ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    ListNode p = dummy;
    // 优先级队列，最小堆
    PriorityQueue<ListNode> pq = new PriorityQueue<>(
        lists.length, (a, b)->(a.val - b.val));
    // 将 k 个链表的头结点加入最小堆
    for (ListNode head : lists) {
        if (head != null)
            pq.add(head);
    }

    while (!pq.isEmpty()) {
        // 获取最小节点，接到结果链表中
        ListNode node = pq.poll();
        p.next = node;
        if (node.next != null) {
            pq.add(node.next);
        }
        // p 指针不断前进
        p = p.next;
    }
    return dummy.next;
}

LeetCode24 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例1

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例2

输入：head = []
输出：[]

示例3

输入：head = [1]
输出：[1]

提示

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

解析

首先题目的示例2、3给了两个特殊情况，先将这两个情况讨论了，然后再实现朴素的两两swap。实现了一组的swap之后我们就能很轻易地想到，我们可以用递归的方法实现剩下的部分。

解答

/**
 * 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* swapPairs(ListNode* head) {
        if (head == nullptr)return nullptr;
        if (head->next == nullptr)return head;
        ListNode *p = head->next;
        head->next = p->next;
        p->next = head;
        head->next = swapPairs(head->next);
        return p;
}
};

LeetCode160相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

解析

如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。

解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。

所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：

那你可能会问，如果说两个链表没有相交点，是否能够正确的返回 null 呢？

这个逻辑可以覆盖这种情况的，相当于 c1 节点是 null 空指针嘛，可以正确返回 null。

按照这个思路，可以写出如下代码：

解答

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p1 = headA, *p2 = headB;
        while(p1 != p2) {
            if (p1 == nullptr) p1 = headB;
            else p1 = p1->next;
            if (p2 == nullptr) p2 = headA;
            else p2 = p2->next;
        }
        return p1;
    }
};

LeetCode206反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

解答

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* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode *last = reverseList(head->next);
        // 注意不是last->next，是head->next->next
        head->next->next = head;
        head->next = nullptr;
        return last;
    }
};

LeetCode148排序链表

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

解析

归并排序。先使用快慢指针找到中点，需要注意快指针初始化需要比慢指针快一步。

使用递归如下：

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* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr){
            return head;
        }
        // 需要注意的是，归并排序快指针初始时需要比慢指针快一步，不然会一直递归下去（最后两个数将永远无法被分割）
        ListNode *fast = head->next, *slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode *mid = slow->next;
        slow->next = nullptr;
        ListNode *left = sortList(head);
        ListNode *right = sortList(mid);
        ListNode *p = new ListNode(-1);
        ListNode *res = p;
        while (left != nullptr && right != nullptr){
            if (left->val < right->val) {
                p->next = left;
                left = left->next;
            }else {
                p->next = right;
                right = right->next;
            }
            p = p->next;
        }
        p->next = left != nullptr ? left : right;
        return res->next;
    }
};

Kiyotaka Wang's Blog

链表

链表

写在前面

LeetCode21 合并两个有序链表

解析：

解答：

LeetCode141 环形链表

解析：

解答：

补充：

LeetCode19 删除链表的倒数第 N 个结点

解析：

解答：

LeetCode86 分隔链表

解析：

解答：

LeetCode23 合并k个升序链表

顺序合并

分治

优先级队列

LeetCode24 两两交换链表中的节点

解析

解答

LeetCode160相交链表

解析

解答

LeetCode206反转链表

解答

LeetCode148排序链表

解析