首页Coding

# 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][1, 100] 内
  • 0≤0 \le Node.val ≤9\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))O(\max(m, n))，其中，mm 和 nn 分别为两链表的长度

空间复杂度：O(1)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))O(\max(m, n))，其中，mm 和 nn 分别为两链表的长度

空间复杂度：O(1)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,104][0, 10^4] 内
  • 1≤1 \le Node.val ≤50\le 50
  • 0≤0 \le val ≤50\le 50

# 思路

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

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

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

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

  1. 若要移除头节点，只需将头节点向后移动一位

  2. 考虑到新的头节点也可能是值为 val ，需要用循环来对头节点进行处理，直到头节点值不为 val

  3. 对头节点以后的其他节点进行遍历，若需移除则按常规方式处理即可

代码实现：

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)O(n)，其中，nn 是链表的长度


空间复杂度：O(1)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≤0 \le  index ,  val  ≤1000\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, 100]
    • 

  • 1≤1 \le  Node.val  ≤100\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)O(N)，其中  N  是给定链表中的结点数目。


空间复杂度：O(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)O(N)，其中  N  是给定链表的结点数目


空间复杂度：O(1)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)O(N)，其中  N  是给定链表的结点数目。


空间复杂度：O(1)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][0, 5000]
    • 

  • −5000≤- 5000 \le  Node.val  ≤5000\le 5000
    • 



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


# Method 1: 双指针


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


算法流程：


    

  1. 定义  cur  指向当前处理节点，初始指向头节点；定义  pre  指向  cur  的上一个节点，初始化为  NULL
    2. 

  2. 遍历  cur ，直到  cur  为空

      

    • 存储  cur  的下一个节点指针（因为接下来要改变  cur->next  ），记作  tmp = cur->next
      • 

    • 修改  cur  的  next  指针的指向，令其指向上一个节点  pre  ，即， cur->next = pre  ，实现反转
      • 

    • pre  和  cur  同时向后移动：执行  pre = cur  ,  cur = tmp
      • 

    

    3. 

  3. 遍历结束时， pre  指向的是原链表的最后一个节点，同时也是反转之后新链表的头节点，因此，返回  pre  即可
    4. 



代码实现：


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)O(n)，其中 nn 为链表长度


空间复杂度：O(1)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)O(n)，其中 nn 为链表长度


空间复杂度：O(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≤0 \le  Node.val  ≤100\le 100
    • 



# 思路


一定要先画图模拟


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


    

  1. 初始时：
    2. 



graph LR
    pre --> cur
    cur --> latter1
    latter1 --> latter2
    

  1. 令  pre  的  next  指针指向  latter1
    2. 



graph LR
    pre -.- cur
    pre --> latter1
    cur --> latter1
    latter1 --> latter2
    

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



graph LR;
    pre --> latter1;
    cur --> latter1;
    latter1 --> cur;
    latter1 -.- latter2;
    

  1. 令  cur  的  next  指针指向  latter2
    2. 



graph LR;
    pre --> latter1;
    latter1 --> cur;
    cur -.- latter1;
    cur --> latter2;
    

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



graph LR;
    pre --> latter1;
    latter1 --> cur;
    cur --> latter2;
# 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(n)


空间复杂度：O(1)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≤1 \le  sz  ≤30\le 30
    • 

  • 0≤0 \le  Node.val  ≤100\le 100
    • 

  • 1≤1 \le  n  ≤\le  sz
    • 



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


# Method: 双指针


解题思路如下：


    

  1. 

    添加一个哑节点（dummy node），即，虚拟头节点，它的  next  指针指向链表的头节点
    

    2. 

  2. 

    定义快慢指针  fast  和  slow  ，初始值为哑结点，然后让  fast  指针移动  n  步，使得  fast  比  slow  超前  n  个节点
    

    3. 

  3. 

    同时移动  fast  和  slow  指针，当  fast  遍历到链表的最后一个节点时（ fast != nullptr && fast->next == nullptr ）， slow  的下一个节点就是需要删除的节点
    

    4. 

  4. 

    修改指针，即， slow->next = slow->next->next  ，完成删除操作
    

    5. 





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




代码实现：


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)O(L)，其中 LL 是链表的长度


空间复杂度：O(1)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≤1 \le  m ,  n  ≤3×104\le 3 \times 10^4
    • 

  • 1≤1 \le  Node.val  ≤105\le 10^5
    • 

  • 0≤0 \le  skipA  < m< m
    • 

  • 0≤0 \le  skipB  < n< n
    • 

  • 如果  listA  和  listB  没有交点， intersectVal  为  0
    • 

  • 如果  listA  和  listB  有交点， intersectVal == listA[skipA] == listB[skipB]
    • 



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


# 思路


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


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


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


# Method: 双指针


算法流程：


    

  1. 

    求出两个链表的长度  m  和  n
    

    2. 

  2. 

    定义指针  curA  指向长链表的头节点，指针  curB  指向短链表的头节点
    

    

    3. 

  3. 

    将指针  curA  移动到第  m - n + 1  个节点，使得两个指针后续可移动步数相同（类似于两链表尾端对齐）
    

    

    4. 

  4. 

    比较  curA  是否与  curB  相同
    

      

    • 若相同，则找到交点
      • 

    • 若不相同，则同时将  curA  和  curB  向后移动，直到  curA  和  curB  到达链表末尾
      • 

    

    5. 

  5. 

    若未找到交点，返回空指针
    

    6. 



代码实现：


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)O(m + n)，其中 mm 和 nn 为两链表长度


空间复杂度：O(1)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,104][0, 10^4]
    • 

  • −105≤-10^5 \le  Node.val  ≤105\le 10^5
    • 

  • pos  为 -1 或者链表中的一个 有效索引
    • 



进阶：你能用 O(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(n)


空间复杂度：O(1)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,104][0, 10^4] 内
    • 

  • −105≤- 10^5 \le  Node.val  ≤105\le 10^5
    • 

  • pos  为 -1 或者链表中的一个 有效索引
    • 



进阶：你是否可以使用 O(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)O(n) ，指针  slow  与指针  index1  走过的长度均不超过链表节点数目 nn


空间复杂度：O(1)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][0, 50]
    • 

  • −100≤-100 \le Node.val ≤100\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)O(m + n)，其中 mm 和 nn 分别是链表  list1  和链表  list2  的长度


空间复杂度：O(m+n)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)O(m + n)，其中 mm 和 nn 分别是链表  list1  和链表  list2  的长度


空间复杂度：O(1)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≤0 \le  k  ≤104\le 10^4
    • 

  • 0≤0 \le  lists[i].length  ≤500\le 500
    • 

  • 104≤10^4 \le  lists[i][j]  ≤104\le 10^4
    • 

  • lists[i]  按 升序 排列
    • 

  • lists[i].length  的总和不超过 10410^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(k2n)O(k^2 n) ，其中，kk 是 lists 中的链表条数，nn 是 lists 中链表的最大长度


    

  • 将链表  ans  与链表  lists[i]  合并的时间复杂度为 O(n+(i−1)×n)=O(i×n)O(n + (i - 1) \times n) = O(i \times n)
    • 

  • 总的时间复杂度为 O(∑i=1n(i×n))=O(k2n)O(\sum\limits_{i = 1}^{n} (i \times n)) = O(k^2 n)
    • 



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


# Method 2: 分治


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


    

  • 首先将 kk 条链表进行配对，将每一对链表进行合并，由此可得到 k/2k / 2 条链表（链表的最大长度为 2n/k2 n / k）
    • 

  • 继续将 k/2k / 2 条链表进行配对，合并每一对链表，可得到 k/4k / 4 条链表（链表的最大长度为 4n/k4 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(kn×log⁡k)O(k n \times \log{k})


    

  • 第 ii 轮合并 k/2ik / 2^i 对链表，其中，合并每一对的时间复杂度为 O(2in)O(2^i n)
    • 

  • 总的时间复杂度为 O(∑i=1n(k2i×2in))=O(kn×log⁡k)O(\sum\limits_{i = 1}^{n} (\frac{k}{2^i} \times 2^i n)) = O(k n \times \log{k})
    • 



空间复杂度：O(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)O(N)，NN 为链表长度，遍历统计、遍历修改皆使用 O(N)O(N) 时间


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


# Method 2: 递归


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


算法流程：


    

  1. 

    终止条件：当  head == nullptr  时，代表越过了链表尾节点，则返回空列表
    

    2. 

  2. 

    递推工作：访问下一节点  head->next
    

    3. 

  3. 

    回溯阶段：将当前节点值  head->val  加入数组  res
    

    4. 



代码实现：


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)O(N)，遍历链表，递归 NN 次


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




注：图解是以 Python 代码为例


# Method 3: 栈


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


算法流程：


    

  1. 

    入栈：遍历链表，将各节点值  push  入栈
    

    2. 

  2. 

    出栈：将各节点值  pop  出栈，存储于数组并返回
    

    3. 



代码实现：


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)O(N)，一共有 NN 次的入栈和出栈

空间复杂度：O(N)O(N)，辅助栈  stack  和数组  res  各使用 O(N)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)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≤1 \le  capacity  ≤\le 3000$
    • 

  • 0≤0 \le  key  ≤104\le 10^4
    • 

  • 0≤0 \le  value  ≤105\le 10^5
    • 

  • 最多调用 2×1052 \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×104][0, 5 \times 10^4]
    • 

  • −105≤-10^5 \le  Node.val  ≤105\le 10^5
    • 



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


# 思路


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


    

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

  • 自底向上归并排序的空间复杂度为 O(1)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(nlog⁡n)O(n \log{n})，其中 nn 是链表的长度


空间复杂度：O(log⁡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(nlog⁡n)O(n \log{n})，其中 nn 是链表的长度


空间复杂度：O(1)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,105][1, 10^5] 内
    • 

  • 0≤0 \le  Node.val  ≤9\le 9
    • 



进阶：你能否用 O(n)O(n) 时间复杂度和 O(1)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)O(n)，其中 nn 是链表的长度


空间复杂度：O(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)O(n)，其中 nn 是链表的长度


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