# LeetCode 2. 两数相加

LeetCode 2. Add Two Numbers

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

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

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 $[1, 100]$ 内
$0 \le$ Node.val $\le 9$
题目数据保证列表表示的数字不含前导零

# 思路

链表的首端对应数的最低位，末端对应数的最高位

将两数相加，即，将两链表相同位置上的节点的值相加

注意，需要考虑进位

将来自前一位的进位值加到当前位
根据当前位的值，更新进位值
若最高位产生进位，则需新增一个更高位

本题采用模拟算法来实现两数相加，即，模拟两数相加的计算过程（列竖式）

# Method: 模拟

# 写法一

将 l1 作为长链，并利用 l1 存储两数之和的结果

代码实现：

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    int num1 = 0, num2 = 0;
    for (ListNode *cur1 = l1; cur1 != nullptr; cur1 = cur1->next)
        num1++;
    for (ListNode *cur2 = l2; cur2 != nullptr; cur2 = cur2->next)
        num2++;
    if (num1 < num2) swap(l1, l2);   // 令 l1 指向长链
    int tag = 0;    // 进位的值
    for (ListNode *cur1 = l1, *cur2 = l2; cur1 != nullptr; cur1 = cur1->next) {
        if (cur2) { // cur2 非空，应计算 cur1 、cur2 、 tag 之和
            cur1->val = cur1->val + cur2->val + tag;
            cur2 = cur2->next;
        } else      // cur2 为空，只计算 cur1 与 tag 之和
            cur1->val = cur1->val + tag;
        tag = cur1->val / 10;     // 更新进位值
        cur1->val %= 10;          // 更新进位后的 cur1->val
        if (!cur1->next && tag) { // 最高位进 1
            cur1->next = new ListNode(tag);
            return l1;
        }
    }
    return l1;
}

时间复杂度： $O(\max(m, n))$ ，其中， $m$ 和 $n$ 分别为两链表的长度

空间复杂度： $O(1)$

# 写法二

定义一个新的链表，存储计算结果

代码实现：

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *head = nullptr;  // head 为结果链表的头节点
    ListNode *cur = nullptr;   // cur 为当前节点（通过 cur  将 head 链表串联起来）
    int carry = 0;             // 进位
    while (l1 || l2) {
        int val1 = l1 ? l1->val : 0, val2 = l2 ? l2->val : 0; // 获取 l1 与 l2 节点的值
        int sum = val1 + val2 + carry; // 计算 l1 与 l2 节点值之和，再加上前一位的进位值
        if (head == nullptr) { // head 为空，将两数之后的最低位值赋给 head
            cur = new ListNode(sum % 10);
            head = cur;
        } else {               // head 不为空，令 cur 下一个节点的值为 sum % 10
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
        }
        carry = sum / 10;      // 更新进位值
        if (l1) l1 = l1->next; // l1 右移
        if (l2) l2 = l2->next; // l2 右移
    }
    if (carry) // 最高位的进位
        cur->next = new ListNode(carry);
    return head;
}

时间复杂度： $O(\max(m, n))$ ，其中， $m$ 和 $n$ 分别为两链表的长度

空间复杂度： $O(1)$ ，这里未考虑存储结果所需的空间

参考：力扣官方题解：两数相加

# LeetCode 203. 移除链表元素

LeetCode 203. Remove Linked List Elements

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

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

示例 2：

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

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

列表中的节点数目在范围 $[0, 10^4]$ 内
$1 \le$ Node.val $\le 50$
$0 \le$ val $\le 50$

# 思路

用 cur 表示当前节点：如果 cur 的下一个节点不为空且下一个节点的值等于给定的 val ，即， cur->next != NULL && cur->next->val == val ，则需要移除 cur 的下一个节点，即： cur->next = cur->next->next

但如果要移除的节点是头节点（它没有上个节点）怎么办？

Method 1：直接将头节点向后移动
Method 2：在头节点前添加一个虚拟节点，使得原链表的所有节点均可按照常规的方式进行移除

# Method 1: 直接使用原链表来进行删除操作

若要移除头节点，只需将头节点向后移动一位
考虑到新的头节点也可能是值为 val ，需要用循环来对头节点进行处理，直到头节点值不为 val
对头节点以后的其他节点进行遍历，若需移除则按常规方式处理即可

代码实现：

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

ListNode* removeElements(ListNode* head, int val) {
    // 删除值为 val 的头节点
    while (head != nullptr && head->val == val) {
        ListNode* tmp = head;
        head = head->next;
        delete tmp;
    }

    // 删除值为 val 的非头节点
    ListNode* cur = head;   // 遍历 cur 节点
    while(cur != nullptr && cur->next != nullptr) { // cur 非空且 cur 的下一个节点非空
        if (cur->next->val == val) {    // 当 cur 的下一个节点的值为 val 时，删除 cur 的下一个节点
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
        }
        else
            cur = cur->next;  // cur 向后移动
    }

    // 返回新的头节点
    return head;
}

注意要从内存中删除移除的节点，清理节点内存

# Method 2: 设置虚拟头节点再进行删除操作

设置一个虚拟头结点，原链表的所有节点便都可按照统一的方式进行移除

例如，给链表添加一个虚拟头结点为新的头结点，若要移除这个旧的头结点元素 1 时，只需将虚拟头节点的 next 指向旧的头节点的下一个节点，然后从内存中删除旧的头节点即可：

注意，在 return 头节点时， return 的应该是虚拟头节点的下一个节点，即， return dummyHead->next;

最后也需要将添加的虚拟头节点 dummyHead 从内存中删掉

代码实现：

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

ListNode* removeElements(ListNode* head, int val) {
    // 设置虚拟头节点
    ListNode* dummyHead = new ListNode(0);  // 创建虚拟头节点
    dummyHead->next = head;                 // 令虚拟头节点指向 head

    // 移除操作
    ListNode* cur = dummyHead;
    while (cur->next != nullptr) {
        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;
}

时间复杂度： $O(n)$ ，其中， $n$ 是链表的长度

空间复杂度： $O(1)$

# LeetCode 707. 设计链表

LeetCode 707. Design Linked List

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性： val 和 next 。 val 是当前节点的值， next 是指向下一个节点的指针 / 引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将不会插入到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例 1：

输入：
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出：
[null, null, null, null, 2, null, 3]

解释：
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示：

$0 \le$ index , val $\le 1000$
请不要使用内置的 LinkedList 库
调用 get 、 addAtHead 、 addAtTail 、 addAtIndex 和 deleteAtIndex 的次数不超过 2000

# 思路

旨在设计链表的五个接口，以实现链表的常见操作：

获取链表第 index 个节点的数值
在链表的最前面插入一个节点
在链表的最后面插入一个节点
在链表第 index 个节点前面插入一个节点
删除链表的第 index 个节点

链表操作的两种方式：

直接使用原来的链表来进行操作
设置一个虚拟头结点再进行操作

# Method: 单链表

接下来以设计单链表的五个接口为例，采用设置虚拟头节点的方式执行相关操作

// 定义链表的结构体
struct LinkedNode {
    int val;
    LinkedNode *next;
    LinkedNode() : val(0), next(nullptr) {}
    LinkedNode(int x) : val(x), next(nullptr) {}
};

class MyLinkedList {

    LinkedNode* dummyHead = new LinkedNode();
    int size;

public:

    // 初始化链表
    MyLinkedList() {
        dummyHead = new LinkedNode(0);    // 虚拟头节点
        size = 0;
    }
    
    // 获取链表第 index 个节点的值
    int get(int index) {
        if (index < 0 || index > (size - 1))
            return -1;
        LinkedNode* cur = dummyHead->next;
        while (index) { // 循环结束时 cur 指向第 index 个节点
            cur = cur->next;
            index--;
        }
        return cur->val;
    }
    
    // 在链表的第一个元素之前插入值为 val 的节点，注意要更新链表长度
    void addAtHead(int val) {
        LinkedNode* newHead = new LinkedNode(val);
        newHead->next = dummyHead->next;
        dummyHead->next = newHead;
        size++;
    }
    
    // 在链表的末尾添加值为 val 的节点，注意要更新链表长度
    void addAtTail(int val) {
        LinkedNode* cur = dummyHead;
        while (cur->next != nullptr)
            cur = cur->next;
        LinkedNode* newTail = new LinkedNode(val);
        cur->next = newTail;
        size++;
    }
    
    // 在链表中的第 index 个节点之前添加值为 val 的节点，注意要更新链表长度
    void addAtIndex(int index, int val) {
        if (index > size)
            return;
        LinkedNode* cur = dummyHead;
        while (index) { // 循环结束时 cur 指向第 index - 1 个节点
            cur = cur->next;
            index--;
        }
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = cur->next;
        cur->next = newNode;
        size++;
    }

    // 删除第 index 个节点，注意要更新链表长度
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        LinkedNode* cur = dummyHead;
        while(index) { // 循环结束时 cur 指向第 index - 1 个节点
            cur = cur->next;
            index--;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        size--;
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

# LeetCode 876. 链表的中间结点

LeetCode 876. Middle of the Linked List

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点

提示：

链表的结点数范围是 $[1, 100]$
$1 \le$ Node.val $\le 100$

# Method 1: 数组

对链表进行遍历，同时将遍历到的元素依次放入数组 A 中。如果我们遍历到了 N 个元素，那么链表以及数组的长度也为 N ，对应的中间节点即为 A[N/2]

ListNode* middleNode(ListNode* head) {
    vector<ListNode*> A = {head};
    while (A.back()->next != NULL)
        A.push_back(A.back()->next);
    return A[A.size() / 2];
}

时间复杂度： $O(N)$ ，其中 N 是给定链表中的结点数目。

空间复杂度： $O(N)$ ，即数组 A 用去的空间。

# Method 2: 单指针

对链表进行两次遍历。第一次遍历时，我们统计链表中的元素个数 N ；第二次遍历时，我们遍历到第 N/2 个元素（链表的首节点为第 0 个元素）时，将该元素返回即可

注意，题目要求「两个中间结点的时候，返回第二个中间结点」。此时，快指针可以前进的条件是：当前快指针和当前快指针的下一个结点都非空。
如果题目要求「在两个中间结点的时候，返回第一个中间结点」，快指针可以前进的条件是：当前快指针的下一个结点和当前快指针的下下一个结点都非空。

ListNode* middleNode(ListNode* head) {
    ListNode *current = head;
    int n = 0;
    while (current != nullptr)      // 统计链表的节点数
    {
        n++;
        current = current->next;
    }
    current = head;
    for (int i = 0; i < n / 2; i++) // 寻找链表的中间节点
        current = current->next;
    return current;
}

时间复杂度： $O(N)$ ，其中 N 是给定链表的结点数目

空间复杂度： $O(1)$ ，只需要常数空间存放变量和指针

# Method 3: 快慢指针

用两个指针 slow 与 fast 一起遍历链表。 slow 一次走一步， fast 一次走两步。那么当 fast 到达链表的末尾时， slow 必然位于中间

ListNode* middleNode(ListNode* head) {
    // 快慢指针，快指针一次前进两步，慢指针一次前进一步
    ListNode *fast = head, *slow = head;
    // 判断条件为：快指针当前节点非空且下一节点都非空。这样才能保证返回第二个中间节点（存在两个中间节点时）
    while (fast != nullptr && fast->next != nullptr)    
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

时间复杂度： $O(N)$ ，其中 N 是给定链表的结点数目。

空间复杂度： $O(1)$ ，只需要常数空间存放 slow 和 fast 两个指针。

题解：链表的中间结点

题解：快慢指针（注意链表长度为偶数时，返回第 2 个结点的细节）

# LeetCode 206. 反转链表

LeetCode 206. Reverse Linked List

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

# Method 1: 双指针

要实现链表的反转，只需改变链表节点 next 指针的指向

算法流程：

定义 cur 指向当前处理节点，初始指向头节点；定义 pre 指向 cur 的上一个节点，初始化为 NULL
遍历 cur ，直到 cur 为空
- 存储 cur 的下一个节点指针（因为接下来要改变 cur->next ），记作 tmp = cur->next
- 修改 cur 的 next 指针的指向，令其指向上一个节点 pre ，即， cur->next = pre ，实现反转
- pre 和 cur 同时向后移动：执行 pre = cur , cur = tmp
遍历结束时， pre 指向的是原链表的最后一个节点，同时也是反转之后新链表的头节点，因此，返回 pre 即可

代码实现：

ListNode* reverseList(ListNode* head) {
    ListNode* temp;
    ListNode* pre = NULL;  // 前置节点
    ListNode* cur = head;  // 当前处理节点
    while(cur) {
        temp = cur->next;  // 保存 cur 的下一个节点
        cur->next = pre;   // 反转
        pre = cur;         // 更新 pre 指针
        cur = temp;        // 更新 cur 指针
    }
    return pre;
}

时间复杂度： $O(n)$ ，其中 $n$ 为链表长度

空间复杂度： $O(1)$

# Method 2: 递归

可以利用递归算法实现上述双指针算法的逻辑，代码如下：

ListNode* reverse(ListNode* pre, ListNode* cur){
    if(cur == NULL) return pre; // 递归终止条件，返回的是反转链表的头节点
    ListNode* temp = cur->next;
    cur->next = pre; // 修改 cur 的 next 指针，指向 pre
    return reverse(cur,temp); // 递归，使 temp 的 next 指针指向 cur
}

ListNode* reverseList(ListNode* head) {
    return reverse(NULL, head);
}

上述算法实质上都是沿着链表的方向 从前往后 翻转指针指向

也可以 从后往前 翻转 next 指针的指向

代码实现：

ListNode* reverseList(ListNode* head) { // 翻转 head->next 的 next 指针，使其指向 head
    if (!head || !head->next) return head; // 递归终止条件
    ListNode* newHead = reverseList(head->next); // 递归，使 head->next->next 的下一个节点变为 head->next
    head->next->next = head; // 使 head->next 的下一个节点变为 head
    head->next = nullptr; // 此时的 head 节点为反转链表的尾节点，next 指针应为空指针
    return newHead;
}

时间复杂度： $O(n)$ ，其中 $n$ 为链表长度

空间复杂度： $O(n)$ ，递归调用的栈空间

参考：代码随想录：翻转链表

# LeetCode 24. 两两交换链表中的节点

LeetCode 24. Swap Nodes in Pairs

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

# 思路

一定要先画图模拟

下面以交换 cur 与 latter1 为例，示意交换两个链表节点的过程：

初始时：

令 pre 的 next 指针指向 latter1

保存指向 latter2 的指针 temp ，并且，令 latter1 的 next 指针指向 cur

令 cur 的 next 指针指向 latter2

通过以上步骤，实现节点 cur 与节点 latter1 的交换，所得链表为：

# Method: 双指针

维护 pre 指针和 cur 指针，依照上述步骤完成 cur 和 cur 下个节点 cur->next 的交换

遍历 cur 指针，直到 cur 为空或 cur->next 为空

若 cur 为空，则链表节点数为偶数，此前的两两交换刚好完成所有节点交换
若 cur 不为空但 cur->next 为空，则链表节点数为奇数，两两交换后还剩最后一个节点，此时无需再进行交换

代码实现：

// 省略了结构体 ListNode 的定义
ListNode* swapPairs(ListNode* head) {
    ListNode* dummyHead = new ListNode(); // 设置虚拟头节点，以便交换 head 节点及其下个节点
    dummyHead->next = head;
    ListNode* cur = head;                 // 当前遍历节点
    ListNode* pre = dummyHead;            // 当前遍历节点 cur 的上个节点
    while (cur != nullptr && cur->next != nullptr) { // 交换 cur 及其下个节点
        // 拷贝指向 cur 下下个节点的指针（因为后续会修改 cur->next->next）
        ListNode* temp = cur->next->next;
        // 令 pre 的 next 指针指向 cur 的下个节点
        pre->next = cur->next;
        // 令 cur 下个节点的 next 指针指向 cur
        cur->next->next = cur;
        // 令 cur 的 next 指针指向 temp
        cur->next = temp;
        // pre 与 cur 同时向后移动
        pre = cur;
        cur = cur->next;
    }
    return dummyHead->next;               // 返回 dummyHead->next
}

时间复杂度： $O(n)$

空间复杂度： $O(1)$

# LeetCode 19. 删除链表的倒数第 N 个结点

LeetCode

给你一个链表，删除链表的倒数第 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 \le$ sz $\le 30$
$0 \le$ Node.val $\le 100$
$1 \le$ n $\le$ sz

进阶：你能尝试使用一趟扫描实现吗？

# Method: 双指针

解题思路如下：

添加一个哑节点（dummy node），即，虚拟头节点，它的 next 指针指向链表的头节点
定义快慢指针 fast 和 slow ，初始值为哑结点，然后让 fast 指针移动 n 步，使得 fast 比 slow 超前 n 个节点
同时移动 fast 和 slow 指针，当 fast 遍历到链表的最后一个节点时（ fast != nullptr && fast->next == nullptr ）， slow 的下一个节点就是需要删除的节点
修改指针，即， slow->next = slow->next->next ，完成删除操作

因为添加了哑结点，如果需要删除的是头节点，同样可以采用上述步骤进行

代码实现：

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyHead = new ListNode(0, head);   // 创建哑结点
    ListNode *fast = dummyHead, *slow = dummyHead; // 初始化 fast 指针和 slow 指针
    for (int i = 0; i < n; i++)
        fast = fast->next;          // fast 指针前进 n 步，即，比 slow 超前 n 步
    while (fast != nullptr && fast->next != nullptr) { // 两指针同时移动，直到 fast 走到最后一个节点
        fast = fast->next;
        slow = slow->next;
    }
    ListNode* node = slow->next;    // 暂存待删除节点
    slow->next = slow->next->next;  // 在链表中删除节点
    delete node;                    // 清除已删除节点的内存

    ListNode* ans = dummyHead->next;
    delete dummyHead;               // 清除哑结点
    return ans;
}

时间复杂度： $O(L)$ ，其中 $L$ 是链表的长度

空间复杂度： $O(1)$

# LeetCode 160. 相交链表

LeetCode 160. Intersection of Two Linked Lists

给你两个单链表的头节点 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 个节点。

示例 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 \le$ m , n $\le 3 \times 10^4$
$1 \le$ Node.val $\le 10^5$
$0 \le$ skipA $< m$
$0 \le$ skipB $< n$
如果 listA 和 listB 没有交点， intersectVal 为 0
如果 listA 和 listB 有交点， intersectVal == listA[skipA] == listB[skipB]

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

# 思路

两链表的交点是指两链表对应 节点的指针相等 （而不是数值相等），因此，需要找出两个链表相交节点的指针

若两链表相交，则两链表的交点及以后节点均对应相等

可将两链表 “尾端对齐” ，从较短链表的头节点开始检查，比较两链表对应节点是否相等

# Method: 双指针

算法流程：

求出两个链表的长度 m 和 n
定义指针 curA 指向长链表的头节点，指针 curB 指向短链表的头节点
将指针 curA 移动到第 m - n + 1 个节点，使得两个指针后续可移动步数相同（类似于两链表尾端对齐）
比较 curA 是否与 curB 相同
- 若相同，则找到交点
- 若不相同，则同时将 curA 和 curB 向后移动，直到 curA 和 curB 到达链表末尾
若未找到交点，返回空指针

代码实现：

int getSize(ListNode *head) { // 计算链表的长度
    int num = 0;
    ListNode *cur = head;
    while (cur != nullptr) {
        num++;
        cur = cur->next;
    }
    return num;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int m = getSize(headA);
    int n = getSize(headB);
    ListNode *curA = headA, *curB = headB;
    if (m < n) {              // curA 指向长链，curB 指向短链
        swap(m, n);
        swap(curA, curB);
    }
    for (int i = 0; i < m - n; i++) // 令 curA 和 curB 的起点一致
        curA = curA->next;
    while (curA != nullptr) { // 遍历 curA 和 curB ，看两者是否相等
        if (curA == curB)
            return curA;
        curA = curA->next;
        curB = curB->next;
    }
    return NULL;    // curA 已经移动到尾后，此时仍未找到交点
}

时间复杂度： $O(m + n)$ ，其中 $m$ 和 $n$ 为两链表长度

空间复杂度： $O(1)$

参考：代码随想录：相交链表

# LeetCode 141. 环形链表

141. Linked List Cycle

给你一个链表的头节点 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, 10^4]$
$-10^5 \le$ Node.val $\le 10^5$
pos 为 -1 或者链表中的一个有效索引

进阶：你能用 $O(1)$ （即，常量）内存解决此问题吗？

# Method: 双指针

算法思路：

定义 fast 和 slow 指针，均从头结点出发

fast 指针每次移动两个节点
slow 指针每次移动一个节点

如果 fast 和 slow 指针在途中相遇，说明链表有环

代码实现：

bool hasCycle(ListNode *head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) return true;
    }
    return false;
}

时间复杂度： $O(n)$

空间复杂度： $O(1)$

# LeetCode 142. 环形链表 II

LeetCode 142. Linked List Cycle II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null 。

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

不允许修改 链表。

示例 1：

示例 1

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

示例 2：

示例 2

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

示例 3：

示例 3

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

提示：

链表中节点的数目范围在范围 $[0, 10^4]$ 内
$- 10^5 \le$ Node.val $\le 10^5$
pos 为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 $O(1)$ 空间解决此题？

# 思路

关键点一：判断是否有环

定义 fast 和 slow 指针，从头结点出发， fast 指针每次移动两个节点， slow 指针每次移动一个节点，如果 fast 和 slow 指针在途中相遇，说明这个链表有环

若 fast 与 slow 相遇，则一定有环：因为 fast 超前 slow ，相遇时二者一定都在环内
若链表有环，则 fast 与 slow 一定相遇：当 slow 步入到环内时，由于 fast 指针每次移动相对于 slow 指针而言都是移动一位，故而一定会相遇

关键点二：确定环的入口

slow 指针在第一次遍历链表环时，就一定会与 fast 指针相遇。具体证明过程见环形链表：补充

假设从头结点到环形入口节点的节点数为 x ，从环形入口节点到 fast 指针与 slow 指针相遇节点的节点数为 y ，从相遇节点再到环形入口节点的节点数为 z

相遇时 slow 指针走过的节点数为 x + y ， fast 指针走过的节点数为 x + y + n (y + z) ，其中 n 为 fast 指针在环内走过的圈数

由于 fast 指针一步两节点， slow 指针一步一节点，则 fast 走过节点数为 slow 指针走过节点数的 2 倍，即： 2 (x + y) = x + y + n (y + z)

故而，环形的入口节点 x 应满足 x = (n - 1) (y + z) + z ，注意 n 一定大于等于 1 （否则， fast 不可能与 slow 相遇）

这意味着，指针 index1 从头结点出发，与此同时，指针 index2 从相遇节点出发，两指针每次均只走一个节点，这两个指针相遇的节点就是环形入口的节点

参考：代码随想录：环形链表 II

# Method: 快慢指针

ListNode *detectCycle(ListNode *head) {
    ListNode *fast = head, *slow = head;
    while (fast != nullptr && fast->next != nullptr) { // fast 到达链表最后一个节点时，循环结束
        // fast 指针每步走两节点，slow 指针每步走一节点
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) { // fast 与 slow 相遇
            // index1 指针从 head 出发，index2 指针从 fast 与 slow 相遇点出发，找出 index1 与 index2 的相遇位置
            ListNode *index1 = head, *index2 = fast;
            while (index1 != index2) {
                index1 = index1->next;
                index2 = index2->next;
            }
            return index1;  // index1 与 index2 的相遇点即为环形入口
        }
    }
    // fast 不与 slow 相遇，不存在环形
    return NULL;
}

时间复杂度： $O(n)$ ，指针 slow 与指针 index1 走过的长度均不超过链表节点数目 $n$

空间复杂度： $O(1)$ ，仅使用指针

# LeetCode 21. 合并两个有序链表

21. Merge Two Sorted Lists

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

示例 1：

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

示例 2：

输入：list1 = [], list2 = []
输出：[]

示例 3：

输入：list1 = [], list2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 $[0, 50]$
$-100 \le$ Node.val $\le 100$
list1 和 list2 均按 非递减顺序 排列

# Method 1: 递归

单层递归的逻辑：

若 list1 == nullptr ，则可取 list2 作为目标链表
若 list2 == nullptr ，则可取 list1 作为目标链表
若 list1->val <= list2->val ，则应将 list1 添加到目标链表，并递归调用 mergeTwoLists(list1->next, list2) 以确定目标链表中的下一个节点，即， list1->next = mergeTwoLists(list1->next, list2)
若 list1->val > list2->val ，则应将 list2 添加到目标链表，并递归调用 mergeTwoLists(list1, list2->next) 以确定目标链表中的下一个节点，即， list2->next = mergeTwoLists(list1, list2->next)

代码实现：

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if (list1 == nullptr) return list2;
    else if (list2 == nullptr) return list1;
    else if (list1->val <= list2->val) {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    } else {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
}

时间复杂度： $O(m + n)$ ，其中 $m$ 和 $n$ 分别是链表 list1 和链表 list2 的长度

空间复杂度： $O(m + n)$ ，递归所需栈空间

# Method 2: 迭代

算法思路：

定义一个虚拟头节点（哑节点） dummyHead ，初始化为 ListNode(0) ，其 next 指针指向目标链表的头节点

定义一个指针 prev 指向目标链接的末尾，初始化 prev 为 dummyHead ，其 next 指针将指向新添加的节点

遍历链表 list1 和 list2 ，直到其中一个链表为空：

若 list1->val <= list2->val ，则应将 list1 添加到目标链表，即 prev->next = list1 ，并将 list1 和 prev 分别向后移动一步
若 list1->val > list2->val ，则应将 list2 添加到目标链表，即 prev->next = list2 ，并将 list2 和 prev 分别向后移动一步

循环结束后， list1 和 list2 最多只有一个非空，直接将目标链表的末尾指向非空链表即可

代码实现：

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* dummyHead = new ListNode();
    ListNode* prev = dummyHead;
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            prev->next = list1;
            list1 = list1->next;
        } else {
            prev->next = list2;
            list2 = list2->next;
        }
        prev = prev->next;
    }
    prev->next = list1 == nullptr ? list2 : list1;
    ListNode* ans = dummyHead->next;
    delete dummyHead;
    return ans;
}

时间复杂度： $O(m + n)$ ，其中 $m$ 和 $n$ 分别是链表 list1 和链表 list2 的长度

空间复杂度： $O(1)$

参考：力扣官方题解

# LeetCode 23. 合并 K 个升序链表

23. Merge k Sorted Lists

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

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

示例 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 \le$ k $\le 10^4$
$0 \le$ lists[i].length $\le 500$
$10^4 \le$ lists[i][j] $\le 10^4$
lists[i] 按升序排列
lists[i].length 的总和不超过 $10^4$

# Method 1: 顺序合并

算法思路：首先将 lists[0] 和 lists[1] 合并，得到链表 ans ，再依次将 ans 与 lists[2] , ... , lists[lists.size() - 1] 合并

代码实现：

ListNode* merge2Lists(ListNode* l1, ListNode* l2) { // 合并链表 l1 和 l2
    ListNode* dummyHead = new ListNode();
    ListNode* tail = dummyHead;
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    ListNode* head = dummyHead->next;
    delete dummyHead;
    return head;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.size() == 0) return nullptr;
    ListNode* ans = lists[0];
    for (int i = 1; i < lists.size(); i++) { // 顺序合并
        ans = merge2Lists(ans, lists[i]);
    }
    return ans;
}

时间复杂度： $O(k^2 n)$ ，其中， $k$ 是 lists 中的链表条数， $n$ 是 lists 中链表的最大长度

将链表 ans 与链表 lists[i] 合并的时间复杂度为 $O(n + (i - 1) \times n) = O(i \times n)$
总的时间复杂度为 $O(\sum\limits_{i = 1}^{n} (i \times n)) = O(k^2 n)$

空间复杂度： $O(1)$

# Method 2: 分治

算法思路：可以用分治的思路来合并，即：

首先将 $k$ 条链表进行配对，将每一对链表进行合并，由此可得到 $k / 2$ 条链表（链表的最大长度为 $2 n / k$ ）
继续将 $k / 2$ 条链表进行配对，合并每一对链表，可得到 $k / 4$ 条链表（链表的最大长度为 $4 n / k$ ）
重复该过程，直到所有链表均已合并完成

代码实现：

ListNode* merge2Lists(ListNode* l1, ListNode* l2) { // 合并链表 l1 和 l2
    ListNode* dummyHead = new ListNode();
    ListNode* tail = dummyHead;
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    ListNode* head = dummyHead->next;
    delete dummyHead;
    return head;
}

ListNode* merge(vector<ListNode*>& lists, int left, int right) { // 合并 [left, right] 索引范围内的链表
    if (left == right) return lists[left];
    if (left > right) return nullptr;
    int mid = (left + right) >> 1;
    ListNode* l1 = merge(lists, left, mid);      // 合并 [left, mid] 索引范围内的链表
    ListNode* l2 = merge(lists, mid + 1, right); // 合并 [mid + 1, right] 索引范围内的链表
    return merge2Lists(l1, l2);                  // 合并成一条链表
}

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

时间复杂度： $O(k n \times \log{k})$

第 $i$ 轮合并 $k / 2^i$ 对链表，其中，合并每一对的时间复杂度为 $O(2^i n)$
总的时间复杂度为 $O(\sum\limits_{i = 1}^{n} (\frac{k}{2^i} \times 2^i n)) = O(k n \times \log{k})$

空间复杂度： $O(\log{k})$ ，递归（ merge 函数）所需栈空间

参考：力扣官方题解

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

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）

示例 1：

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

# Method 1: 遍历添加

链表长度未知

先统计链表节点的个数 count ，然后定义一个数组，逆序记录链表各节点的值

vector<int> reversePrint(ListNode* head) {
    // 统计链表的节点数
    int count = 0;
    ListNode *node = head;
    while (node != nullptr) {
        count++;
        node = node->next;
    }
    // 创建数组
    vector<int> nums(count,0);
    // 逆序记录链表节点的值
    node = head;
    for (int i = count - 1; node != nullptr; i--) {
        nums[i] = node->val;
        node = node->next;
    }
    return nums;
}

时间复杂度： $O(N)$ ， $N$ 为链表长度，遍历统计、遍历修改皆使用 $O(N)$ 时间

空间复杂度： $O(N)$ ，新建了一个 vector 容器

# Method 2: 递归

利用递归，先递推至链表末端；回溯时，依次将节点值加入数组，即可实现链表值的逆序输出

算法流程：

终止条件：当 head == nullptr 时，代表越过了链表尾节点，则返回空列表
递推工作：访问下一节点 head->next
回溯阶段：将当前节点值 head->val 加入数组 res

代码实现：

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        recur(head);
        return res;
    }

private:
    vector<int> res;
    void recur(ListNode *head) {
        if(head == nullptr) return;
        recur(head->next);
        res.push_back(head->val);
    }
};

时间复杂度： $O(N)$ ，遍历链表，递归 $N$ 次

空间复杂度： $O(N)$ ，递归需要使用 $O(N)$ 的栈空间

注：图解是以 Python 代码为例

# Method 3: 栈

链表只能从前至后访问每个节点，而这里要求 逆序输出 各节点值，这种 先入后出 的需求可以借助栈来实现

算法流程：

入栈：遍历链表，将各节点值 push 入栈
出栈：将各节点值 pop 出栈，存储于数组并返回

代码实现：

vector<int> reversePrint(ListNode* head) {
    stack<int> stk;
    while(head != nullptr) {
        stk.push(head->val);        // 入栈，在栈顶增加元素
        head = head->next;
    }
    vector<int> res;
    while(!stk.empty()) {           // 判断堆栈是否为空
        res.push_back(stk.top());   // top() 函数返回栈顶元素
        stk.pop();                  // 出栈，移除栈顶元素
    }
    return res;
}

时间复杂度： $O(N)$ ，一共有 $N$ 次的入栈和出栈
空间复杂度： $O(N)$ ，辅助栈 stack 和数组 res 各使用 $O(N)$ 的额外空间

# LeetCode 146. LRU 缓存

146. LRU Cache

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 $O(1)$ 的平均时间复杂度运行。

示例 1：

输入：
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出：
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释：
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

$1 \le$ capacity $\le$ 3000$
$0 \le$ key $\le 10^4$
$0 \le$ value $\le 10^5$
最多调用 $2 \times 10^5$ 次 get 和 put

# Method: 哈希表 + 双向链表

思路：

可以用一个哈希表和一个双向链表维护所有在 LRU 缓存中的键值对

双向链表按照被使用的顺序存储键值对：靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的
哈希表即为普通的哈希映射（HashMap），通过缓存数据的关键字 key 映射其在双向链表中的位置

因此，我们可以先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 的时间内完成 get 或者 put 操作

特别地，在双向链表的实现中，可以添加一个虚拟头部（dummy head）和虚拟尾部（dummy tail）。于是，添加节点和删除节点时，不需要再检查相邻的节点是否存在

代码实现：

struct DLinkedNode { // 双向链表
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> hash;
    DLinkedNode* head; // 虚拟头节点
    DLinkedNode* tail; // 虚拟尾节点
    int _capacity;     // 缓存的容量
    int _size;         // 当前占用的缓存大小

public:
    LRUCache(int capacity) { // 初始化
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
        _size = 0;
        _capacity = capacity;
    }
    
    int get(int key) {
        if (!hash.count(key)) return -1; // key 不存在
        DLinkedNode* node = hash[key];   // key 已存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (hash.count(key)) { // key 已存在，通过哈希表定位，修改数据值，并移到头部
            DLinkedNode* node = hash[key];
            node->value = value;
            moveToHead(node);
        } else { // key 不存在，创建一个新的节点，添加到链表头部，并建立哈希表索引
            DLinkedNode* node = new DLinkedNode(key, value);
            addToHead(node);
            hash[key] = node;
            ++_size;
            if (_size > _capacity) { // 超出容量，需删除最久未使用的关键字
                DLinkedNode* removed = tail->prev; // 需移除的节点（即，虚拟尾节点的前一个节点）
                removeNode(removed);      // 从链表中移除
                hash.erase(removed->key); // 从哈希表中移除
                delete removed;           // 从内存中删除
                --_size;
            }
        }
    }

    void removeNode(DLinkedNode* node) { // 将 node 从链表中移除
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addToHead(DLinkedNode* node) { // 将 node 添加到链表头部
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void moveToHead(DLinkedNode* node) { // 将 node 移至链表头部
        removeNode(node);
        addToHead(node);
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

参考：leetcode-solution

# LeetCode 148. 排序链表

148. Sort List

给你链表的头结点 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 \times 10^4]$
$-10^5 \le$ Node.val $\le 10^5$

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

# 思路

时间复杂度为 $O(n \log{n})$ 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 $O(n^2)$ ）。其中，最适合链表的排序算法是归并排序

考虑到递归调用的栈空间，自顶向下归并排序的空间复杂度为 $O(\log{n})$
自底向上归并排序的空间复杂度为 $O(1)$

# Method 1: 自顶向下归并排序

算法思路：

定义一个递归函数，用于实现对区间 [head, tail) 的归并排序

递归的终止条件：链表的节点个数小于或等于 1，无需再对链表进行拆分和排序，当前递归结束

特别地，为便于后续进行归并，应将单个链表节点的 next 指针置为空（用于标记子链表的末尾）

单层递归的逻辑：

使用快慢指针找到链表的中点
以中点为分界，将链表拆分成两个子链表
对两个子链表分别排序
将两个排序后的子链表合并（归并）

代码实现：

ListNode* sortList(ListNode* head) {
    return mergeSort(head, nullptr);
}

ListNode* mergeSort(ListNode* head, ListNode* tail) { // 对区间 [head, tail) 进行归并排序
    if (head == nullptr) return nullptr;
    if (head->next == tail) {
        head->next = nullptr;
        return head;
    }
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast != tail && fast->next != tail) { // 快慢指针，找出区间 [head, tail) 中点
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode* list1 = mergeSort(head, slow); // 对区间 [head, slow) 进行归并排序
    ListNode* list2 = mergeSort(slow, tail); // 对区间 [slow, tail) 进行归并排序
    return merge(list1, list2); // 归并
}

ListNode* merge(ListNode* head1, ListNode* head2) { // 归并
    ListNode* dummyHead = new ListNode();
    ListNode* cur = dummyHead;
    ListNode* temp1 = head1;
    ListNode* temp2 = head2;
    while (temp1 != nullptr && temp2 != nullptr) {
        if (temp1->val < temp2->val) {
            cur->next = temp1;
            temp1 = temp1->next;
        } else {
            cur->next = temp2;
            temp2 = temp2->next;
        }
        cur = cur->next;
    }
    cur->next = temp1 == nullptr ? temp2 : temp1;
    return dummyHead->next;
}

时间复杂度： $O(n \log{n})$ ，其中 $n$ 是链表的长度

空间复杂度： $O(\log{n})$ ，考虑了递归调用的栈空间

# Method 2: 自底向上归并排序

算法思路：

首先求得链表的长度 length，然后将链表拆分成子链表进行合并

用 subLength 表示每次需要排序的子链表的长度，初始时 subLength = 1
将链表拆分成若干个长度为 subLength 的子链表（最后一个子链表的长度可以小于 subLength），按照每两个子链表一组进行归并
将 subLength 的值加倍，重复第 2 步，对更长的有序子链表进行归并，直到有序子链表的长度大于或等于 length，整个链表排序完毕

代码实现：

ListNode* sortList(ListNode* head) {
    // 计算链表长度
    int length = 0;
    for (ListNode* tmp = head; tmp != nullptr; tmp = tmp->next)
        ++length;
    
    // 拆分链表
    ListNode* dummyHead = new ListNode(0, head); // 虚拟头节点
    for (int subLength = 1; subLength < length; subLength = subLength << 1) { // 遍历每次排序的子链表的长度
        ListNode* prev = dummyHead; // 指向已归并的子链表的末尾
        ListNode* cur = dummyHead->next;
        // 按照每两个子链表一组进行合并
        while (cur != nullptr) {
            ListNode* head1 = cur;  // 第一段子链表的头部
            for (int i = 1; i < subLength && cur->next != nullptr; ++i)
                cur = cur->next;
            ListNode* head2 = cur->next; // 第二段子链表的头部
            cur->next = nullptr;    // 断开第一段子链表与第二段子链表
            cur = head2;
            for (int i = 1; i < subLength && cur != nullptr && cur->next != nullptr; ++i)
                cur = cur->next;
            ListNode* node = nullptr;
            if (cur != nullptr) {
                node = cur->next;    // 剩余链表的头部
                cur->next = nullptr; // 断开第二段子链表与剩余链表
            }
            ListNode* merged = merge(head1, head2); // 将第一段子链表与第二段子链表归并
            prev->next = merged;     // 将归并完成的链表进行连接
            while (prev->next != nullptr) // 更新 prev
                prev = prev->next;
            cur = node;              // 对剩余链表继续拆分（排序）
        }
    }
    return dummyHead->next;
}

ListNode* merge(ListNode* head1, ListNode* head2) { // 归并
    ListNode* dummyHead = new ListNode();
    ListNode* cur = dummyHead;
    ListNode* temp1 = head1;
    ListNode* temp2 = head2;
    while (temp1 != nullptr && temp2 != nullptr) {
        if (temp1->val < temp2->val) {
            cur->next = temp1;
            temp1 = temp1->next;
        } else {
            cur->next = temp2;
            temp2 = temp2->next;
        }
        cur = cur->next;
    }
    if (temp1 != nullptr) cur->next = temp1;
    else cur->next = temp2;
    return dummyHead->next;
}

时间复杂度： $O(n \log{n})$ ，其中 $n$ 是链表的长度

空间复杂度： $O(1)$

参考：leetcode-solution

# LeetCode 234. 回文链表

234. Palindrome Linked List

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

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

提示：

链表中节点数目在范围 $[1, 10^5]$ 内
$0 \le$ Node.val $\le 9$

进阶：你能否用 $O(n)$ 时间复杂度和 $O(1)$ 空间复杂度解决此题？

# Method 1: 栈

算法思路：先将所有链表节点入栈（栈具有先进后出的特点），然后将栈顶元素的值与原链表的值进行比较，并依次出栈

代码实现：

bool isPalindrome(ListNode* head) {
    stack<ListNode*> stk;
    ListNode* cur = head;
    while (cur) {
        stk.push(cur);
        cur = cur->next;
    }
    cur = head;
    ListNode* tmp = nullptr;
    while (cur) {
        tmp = stk.top();
        if (tmp->val != cur->val) return false;
        stk.pop();
        cur = cur->next;
    }
    return true;
}

时间复杂度： $O(n)$ ，其中 $n$ 是链表的长度

空间复杂度： $O(n)$

# Method 2: 双指针

算法思路：

首先利用快慢指针找出链表的中间节点，将链表分割成两个子链表（如果链表节点数为奇数，则将中间节点划入第一个子链表）

若链表节点数为奇数，快慢指针的最终位置应为：慢指针应指向正中间的节点，快指针指向最后一个节点
若链表节点数为奇数，快慢指针的最终位置应为：慢指针应指向左侧的中间节点，快指针指向倒数第二个节点
由此可推断出，移动快慢指针的条件为： fast->next != nullptr && fast->next->next != nullptr

然后反转第二个子链表，将第一个子链表与反转后的第二个子链表进行比较，若对应节点值相等，则原链表为回文链表，否则，原链表不是回文链表

最后，需要将链表恢复原样

代码实现：


ListNode* findMidPoint(ListNode* head) { // 寻找链表的中间节点
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast->next && fast->next->next) { // 快指针移动到链表末尾，慢指针移动到链表中间
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

ListNode* reverseLinkedList(ListNode* head) { // 反转链表
    ListNode* pre = nullptr;
    ListNode* cur = head;
    ListNode* tmp = nullptr;
    while (cur) {
        tmp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
}

bool isPalindrome(ListNode* head) {
    if (head == nullptr) return true;
    ListNode* midpoint = findMidPoint(head); // 链表的中间节点
    ListNode* temp1 = head; // 第一段子链表的头部
    ListNode* head2 = reverseLinkedList(midpoint->next); // 第二段子链表的头部
    ListNode* temp2 = head2;
    while (temp2 != nullptr) {
        if (temp1->val != temp2->val) break;
        temp1 = temp1->next;
        temp2 = temp2->next;
    }
    bool ans = (temp2 == nullptr);
    midpoint->next = reverseLinkedList(head2); // 还原链表
    return ans;
}

时间复杂度： $O(n)$ ，其中 $n$ 是链表的长度

空间复杂度： $O(1)$

链表

# LeetCode 2. 两数相加

# 思路

# Method: 模拟

# 写法一

# 写法二

# LeetCode 203. 移除链表元素

# 思路

# Method 1: 直接使用原链表来进行删除操作

# Method 2: 设置虚拟头节点再进行删除操作

# LeetCode 707. 设计链表

# 思路

# Method: 单链表

# LeetCode 876. 链表的中间结点

# Method 1: 数组

# Method 2: 单指针

# Method 3: 快慢指针

# LeetCode 206. 反转链表

# Method 1: 双指针

# Method 2: 递归

# LeetCode 24. 两两交换链表中的节点

# 思路

# Method: 双指针

# LeetCode 19. 删除链表的倒数第 N 个结点

# Method: 双指针

# LeetCode 160. 相交链表

# 思路

# Method: 双指针

# LeetCode 141. 环形链表

# Method: 双指针

# LeetCode 142. 环形链表 II

# 思路

# Method: 快慢指针

# LeetCode 21. 合并两个有序链表

# Method 1: 递归

# Method 2: 迭代

# LeetCode 23. 合并 K 个升序链表

# Method 1: 顺序合并

# Method 2: 分治

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

# Method 1: 遍历添加

# Method 2: 递归

# Method 3: 栈

# LeetCode 146. LRU 缓存

# Method: 哈希表 + 双向链表

# LeetCode 148. 排序链表

# 思路

# Method 1: 自顶向下归并排序

# Method 2: 自底向上归并排序

# LeetCode 234. 回文链表

# Method 1: 栈

# Method 2: 双指针

算法复杂度

LeetCode - 数组专题