leetcode刷题系列之链表

这篇文章是leetcode刷题系列的第2部分——链表，链表的大部分题目难度都不大。leetcode上链表部分的题目也就40道左右，基本上都做了，这里就把有代表性的题目发出来，共计24道。每道题都给出了注释，有的题目还给出了另一种思路和解法。

leetcode刷题系列其它文章组织如下：

1. 数组

2. 链表

3. 字符串

4. 二叉树

5. 队列和栈

6. 动态规划

7. 数据结构设计

8. 刷题小知识点

206. Reverse Linked List

给定一个单链表的头节点，反转链表，然后返回反转后的链表头节点。

// 迭代解法
ListNode* reverseList(ListNode* head) {
    ListNode* p = nullptr;
    ListNode* q = p;
    while(head) {
        q = head->next;
        
        head->next = p;
        p = head;
        
        head = q;
    }
    return p;
}

// 递归解法
ListNode* reverseList(ListNode* head) {
    if(!head || !head->next) {
        return head;
    }
    ListNode* q = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return q;
}

92. Reverse Linked List II

给定一个单链表的头以及left和right两个整数，其中left <= right，将链表中从left位置到right位置的节点反转，返回反转后的链表。

// 头插法
// 鲁棒性编码，如果输入无效参数，函数返回空指针
// 输入有效则返回反转后链表的头节点
ListNode *reverseBetween(ListNode *head, int left, int right) {
    if(head == nullptr || left < 1 || left > right) {
        return nullptr;
    }
    ListNode helper(0, head);
    ListNode* preTheLeft = &helper;
    for(int i = 0; i < left - 1; i++) {
        if(preTheLeft->next) {
            preTheLeft = preTheLeft->next;
        }
        else {
            return nullptr;
        }
    }
    ListNode* preToInsert = preTheLeft->next;
    ListNode* ToInsert = nullptr;
    for(int i = 0; i < right - left; i++) {
        if(preToInsert->next) {
            ToInsert = preToInsert->next;
        }
        else {
            return nullptr;
        }
        preToInsert->next = ToInsert->next;
        ToInsert->next = preTheLeft->next;
        preTheLeft->next = ToInsert;
    }
    return helper.next;
}

/* 纯递归解法 */
// 反转整个链表
ListNode* reverseList(ListNode* head) {
    if(!head || !head->next) {
        return head;
    }
    ListNode* q = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return q;
}
// 反转前 n 个节点
ListNode* reverseN(ListNode* head, int n) {
    ListNode* p = head;
    while(--n > 0) {
        p = p->next;
    }
    ListNode* q = p->next;
    p->next = nullptr;
    p = reverseList(head);
    head->next = q;
    return p;
}

ListNode* reverseBetween(ListNode* head, int left, int right) {
    if(left == 1) {
        return reverseN(head, right);
    }
    head->next = reverseBetween(head->next, left - 1, right - 1);
    return head;
}

/* 纯迭代解法 */
// 反转整个链表
ListNode* reverseList(ListNode* head) {
    ListNode* p = nullptr;
    ListNode* q = p;
    while(head) {
        q = head->next;
        head->next = p;
        p = head;
        head = q;
    }
    return p;
}
// 反转前 n 个节点
ListNode* reverseN(ListNode* head, int n) {
    ListNode* p = head;
    while(--n > 0) {
        p = p->next;
    }
    ListNode* q = p->next;
    p->next = nullptr;
    ListNode* r = reverseList(head);
    head->next = q;
    return r;
}

ListNode* reverseBetween(ListNode* head, int left, int right) {
    if(left == 1) {
        return reverseN(head, right);
    }
    // 计算反转的实际节点数
    int n = right - left + 1;
    ListNode* preLeft = head;
    left--;
    while(--left > 0) {
        preLeft = preLeft->next;
    }
    // preLeft 现在指向第 left 个节点的前一个节点
    preLeft->next = reverseN(preLeft->next, n);
    return head;
}

25. Reverse Nodes in k-Group

给你一个链表，每k个节点一组进行翻转，请你返回翻转后的链表。k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：你可以设计一个只使用常数额外空间的算法来解决此问题吗？不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

Example 1 Example 2

ListNode* reverseKGroup(ListNode* head, int k) {
    if(head == nullptr || k <= 1) {
        return head;
    }
    ListNode helper(0, head);
    // last 始终指向新链表的末尾节点, 方便后续链表接在其后面
    // last->next 就一直指向正在反转的局部链表
    ListNode* last = &helper;
    // cur 用于遍历每一个节点
    ListNode* cur = last;
    // 反转整个链表
    auto reverseList = [](ListNode* head) {
        ListNode* reversedHead = nullptr;
        ListNode* needToReverse = nullptr;
        while(head) {
            needToReverse = head->next;
            head->next = reversedHead;
            reversedHead = head;
            head = needToReverse;
        }
        return reversedHead;
    };
    while(1) {
        for(int i = 0; i < k && cur; i++) {
            cur = cur->next;
        }
        if(cur == nullptr) {
            break;
        }
        // nextToReverse 始终指向后面待反转的链表的头节点
        ListNode* nextToReverse = cur->next;
        cur->next = nullptr;
        
        cur = last->next;
        last->next = reverseList(last->next);
        cur->next = nextToReverse;
        last = cur;
    }
    return helper.next;
}

struct Node {
    Node* next;
    int val;
    Node(int _val, Node* _next) : val(_val), next(_next) {
}
};

Node* reverseKGroup(Node* head, int k) {
    if(head == nullptr) {
        return head;
    }
    Node helper(0, head);
    Node* last = &helper;
    Node* curNode = last;
    auto reverse = [](Node* head) {
        Node* p = nullptr;
        Node* q = nullptr;
        while(head) {
            q = head->next;
            head->next = p;
            p = head;
            head = q;
        }
        return p;
    };
    while(1) {
        for(int i = 0; i < k; i++) {
            if(curNode->next) {
                curNode = curNode->next;
            }
            else {
                last->next = reverse(last->next);
                curNode = nullptr;
                break;
            }
        }
        if(curNode == nullptr) {
            break;
        }
        Node* temp = curNode->next;
        curNode->next = nullptr;
        curNode = last->next;
        last->next = reverse(last->next);
        curNode->next = temp;
        last = curNode;
    }
    return helper.next;
}

int main() {
    Node head(0, nullptr);
    Node* last = &head;
    for(int i = 1; i <= 8; i++) {
        last->next = new Node(i, nullptr);
        last = last->next;
    }
    Node* newHead = reverseKGroup(head.next, 3);
    for(auto* it = newHead; it; it = it->next) {
        cout << it->val << " ";
    }
}

382. Linked List Random Node

给定一个单链表，从链表随机返回一个节点的值。每个节点必须具有相同的被选择概率。

如果链表很大并且你不知道其长度怎么办？你能在不使用额外空间的情况下有效解决此问题吗？

如果随机返回k个节点的值呢？

水塘抽样算法：遇到第i个元素时，应该有1/i的概率选择该元素，1 - 1/i的概率保持原有的选择。

证明：假设总共有n个元素，我们要的随机性无非就是每个元素被选择的概率都是1/n ，那么对于第i个元素，它被选择的概率就是：

同理，如果要随机选择k个数，只要在第i个元素处以k/i的概率选择该元素，以1 - k/i的概率保持原有选择即可。

证明：略。

/* Returns a random node's value. */
int getRandom(ListNode* head) {
    int res = 0, i = 0;
    while(head) {
        i++;
        int j = rand() % i;
        // j 等于 0 的概率就为 1/i
        if(j == 0) {
            res = head->val;
        }
        head = head->next;
    }
    return res;
}

/* Returns k random node's value. */
vector<int> getRandom(ListNode* head, int k) {
    vector<int> res(k, 0);
    // 前 k 个值默认先选上
    for(int i = 0; i < k && head; i++) {
        res[i] = head->val;
        head = head->next;
    }
    int i = k;
    while(head) {
        i++;
        int j = rand() % i;
        // j 小于 k 的概率就为 k/i
        if(j < k) {
            res[j] = head->val;
        }
        head = head->next;
    }
    return res;
}

2. Add Two Numbers

给定两个表示两个非负整数的非空链表。这些数字以相反的顺序存储，即低位数在前，并且它们的每个节点都包含一个数字。将两个数字相加并返回总和作为链接列表。

ListNode* addTwoNumbers(ListNode* p, ListNode* q) {
    ListNode head;
    ListNode* last = &head;
    int sum = 0, carry = 0;
    while(p || q) {
        if(p) {
            sum += p->val;
            p = p->next;
        }
        if(q) {
            sum += q->val;
            q = q->next;
        }
        sum += carry;
        last->next = new ListNode(sum % 10);
        last = last->next;
        carry = sum / 10;
        sum = 0;
    }
    if(carry > 0) {
        last->next = new ListNode(carry);
    }
    return head.next;
}

445. Add Two Numbers II

给定两个表示两个非负整数的非空链表。高位数字在前，并且它们的每个节点都包含一个数字。将两个数字相加，然后将其作为链表返回。

如果无法修改输入列表怎么办？换句话说，不允许反转列表。

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

// 借助栈后进先出的特性即可
// 只不过插入新节点的时候注意插在头部
// 另外将外面的两个 while 循环拿进去, 减少重复代码, 更优美
ListNode* addTwoNumbers(ListNode* p, ListNode* q) {
    stack<ListNode*> pStack, qStack;
    while(p) {
        pStack.push(p);
        p = p->next;
    }
    while(q) {
        qStack.push(q);
        q = q->next;
    }
    ListNode* head = nullptr;
    int carry = 0;
    while(!pStack.empty() || !qStack.empty()) {
        int sum = 0;
        if(!pStack.empty()) {
            sum += pStack.top()->val;
            pStack.pop();
        }
        if(!qStack.empty()) {
            sum += qStack.top()->val;
            qStack.pop();
        }
        sum += carry;
        head = new ListNode(sum % 10, head);
        carry = sum / 10;
    }
    if(carry > 0) {
        head = new ListNode(carry, head);
    }
    return head;
}

1721. Swapping Nodes in a Linked List

给定一个链表的头以及一个整数k。将从头开始第k个节点的值与从结尾开始第k个节点的值交换，返回链表的头。

Input: head = [1, 2, 3, 4, 5], k = 2
Output: [1, 4, 3, 2, 5]

// 左右双指针的解法
ListNode* swapNodes(ListNode* head, int k) {
    ListNode* left = nullptr;
    ListNode* p = head;
    while(--k > 0) {
        p = p->next;
    }
    left = p;
    // 此时 left 指向从左边数第 k 个节点
    ListNode* right = head;
    while(p->next) {
        right = right->next;
        p = p->next;
    }
    // 此时 right 指向从右边数第 k 个节点
    swap(left->val, right->val);
    return head;
}

109. Convert Sorted List to Binary Search Tree

给定一个单链表的头，其中元素按升序排序，请将其转换为高度平衡的BST。结果不唯一。

在此处，高度平衡的二叉树定义为这样一棵二叉树，其中每个节点的两个子树的深度相差不超过1。

// 基本思想是将链表的左半部分节点作为 BST 的左子树, 右半部分节点作为 BST 的右子树,
// 然后进行递归调用就可以了, 每次只需要处理中间节点即可
// 这样可保证 BST 是高度平衡的
// 同样的, 如果给的是有序数组, 也可以利用将中间元素构造成根节点的递归思路
// 分治的思路, 所以时间复杂度为 O(nlogn), 递推式为 T(n) = T(n/2) + O(n)
// 递归过程中空间复杂度取决于树的最大深度为 O(logn)
TreeNode* sortedListToBST(ListNode* head) {
    if(!head) {
        return nullptr;
    }
    if(!head->next) {
        return new TreeNode(head->val);
    }
    // 先定位到链表的中间节点
    ListNode* slow = head;
    ListNode* fast = head;
    ListNode* preSlow = head;
    while(fast && fast->next) {
        preSlow = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    // 此时 slow 指向中间节点, preSlow 指向其前一节点
    // 将左半部分子链表分离
    preSlow->next = nullptr;
    // 将中间节点构建成 BST 的根节点
    TreeNode* root = new TreeNode(slow->val);
    root->left = sortedListToBST(head);
    root->right = sortedListToBST(slow->next);
    return root;
}

// 上一方法时间复杂度的瓶颈在于寻找中间节点
// 由于构造出来的二叉搜索树的中序遍历结果就是给定的链表
// 因此, 我们假想二叉搜索树已经存在了
// 对此二叉搜索树进行中序遍历, 遍历的同时更新树中的节点
TreeNode* sortedListToBST(ListNode* head) {
    int size = 0;
    for(ListNode* temp = head; temp; temp = temp->next, size++);
    auto inOrder = [&](auto&& inOrder, int left, int right) {
        if(left > right) {
            return (TreeNode*)nullptr;
        }
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode;
        root->left = inOrder(inOrder, left, mid - 1);
        root->val = head->val;
        head = head->next;
        root->right = inOrder(inOrder, mid + 1, right);
        return root;
    };
    return inOrder(inOrder, 0, size - 1);
}

141. Linked List Cycle

给定链表的头节点，确定链表中是否有环。如果链表中有一个循环，则返回true。否则，返回false。

// 快慢指针
bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next) {
        // 慢指针每次走一步
        slow = slow->next;
        // 快指针每次走两步
        fast = fast->next->next;
        // 如果相遇就有环
        if(slow == fast) {
            return true;
        }
    }
    return false;
}

142. Linked List Cycle II

给定一个链表头节点，返回环开始的节点。如果没有环，则返回null。

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

fast一定比slow多走了k步，这多走的k步其实就是fast指针在环里转圈圈，所以k的值就是环长度的「整数倍」。设相遇点距环的起点的距离为m，那么环的起点距头结点head的距离为k - m，也就是说如果从head前进k - m步就能到达环起点。

巧的是，如果从相遇点继续前进k - m步，也恰好到达环起点。你甭管fast在环里到底转了几圈，反正走k步可以到相遇点，那走k - m步一定就是走到环起点了：

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) {
            break;
        }
    }
    // 如果不是因为相遇才出循环的
    if(fast == nullptr || fast->next == nullptr) {
        return nullptr;
    }
    slow = head;
    while(slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

876. Middle of the Linked List

给定一个链表头节点，返回链表的中间节点。

可以让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。当链表的长度是奇数时，slow恰巧停在中点位置；如果长度是偶数，slow最终的位置是中间偏右。

链表的归并排序：对于链表，合并两个有序链表是很简单的，难点就在于二分。但是现在知道了找到链表的中点的方法，就能实现链表的二分了。

// 版本一
// 节点个数为偶数时, 返回指向中间两个节点的第二个节点
// 为奇数时返回指向中间的节点
ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 版本二, 在写链表的归并排序时, 要用这个版本!
// 节点个数为偶数时, 返回指向中间两个节点的第一个节点
// 为奇数时返回指向中间的节点的前一个节点
ListNode* middleNode(ListNode* head) {
    ListNode* slow = nullptr;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow ? slow->next : head;
        fast = fast->next->next;
    }
    return slow;
}

19. Remove Nth Node From End of List

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

Example:
1
2
>Input: head = [1,2,3,4,5], n = 2
>Output: [1,2,3,5]

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* slow = head;
    ListNode* fast = head;
    while(n-- > 0 && fast) {
        fast = fast->next;
    }
    if(!fast) {
        return head->next;
    }
    while(fast->next) {
        slow = slow->next;
        fast = fast->next;
    }
    slow->next = slow->next->next;
    return head;
}

160. Intersection of Two Linked Lists

给定两个单链列表headA和headB的头，返回两个列表相交的节点。如果两个链接列表完全没有交集，则返回null。

例如，以下两个链接列表开始在节点c1处相交：

// 先制造出一个环来, 再借助返回环起点的思路
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    if(!headA || !headB) {
        return nullptr;
    }
    ListNode* p = headA;
    while(p->next) {
        p = p->next;
    }
    // 将 A 链表的首尾相连成环
    p->next = headA;
    ListNode* slow = headB;
    ListNode* fast = headB;
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast) {
            break;
        }
    }
    // 如果没有相遇, 说明原先不存在交点
    if(!fast || !fast->next) {
        // 恢复链表 A
        p->next = nullptr;
        return nullptr;
    }
    slow = headB;
    while(slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    // 最后别忘了恢复链表 A
    p->next = nullptr;
    return slow;
}

// 很秀的思路
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *A = headA, *B = headB;
    while(A != B) {
        A = A ? A->next : headB;
        B = B ? B->next : headA;
    }
    return A;
}

328. Odd Even Linked List

给定一个单链列表的头，将所有具有奇数索引的节点组合在一起，然后再加上具有偶数索引的节点，然后返回重新排序的列表。

第一个节点被认为是奇数，第二个节点被认为是偶数，依此类推。请注意，偶数和奇数组中的相对顺序应保持输入中的原样。

Could you solve it in O(1) space complexity and O(nodes) time complexity?

ListNode* oddEvenList(ListNode* head) {
    if(head == nullptr) {
        return head;
    }
    ListNode* oddLast = head;
    ListNode* evenHead = head->next;
    ListNode* evenLast = evenHead;
    while(evenLast && evenLast->next) {
        oddLast->next = evenLast->next;
        oddLast = oddLast->next;
        evenLast->next = oddLast->next;
        evenLast = evenLast->next;
    }
    oddLast->next = eHead;
    return head;
}

234. Palindrome Linked List

给定一个单链表的头节点，如果它是回文链表，则返回true。例如，下面这个就为回文链表：

// 链表的后序遍历结合左右指针
// 利用系统栈来后进先出节点
bool isPalindrome(ListNode* left)
{
    bool res = true;
    function<void(ListNode*)> traverse = [&](ListNode* right) {
        if(right == nullptr) {
            return;
        }
        traverse(right->next);
        res = res && (left->val == right->val);
        // 左指针前进
        left = left->next;
        // 结束一个递归实例后, 右指针会自动后退
    };
    traverse(left);
    return res;
}

// 找到链表的中间节点
// 再将后半部分链表反转, 判断
bool isPalindrome(ListNode* head) {
    // 零个或一个节点的链表默认是回文链表
    if(head == nullptr || head->next == nullptr) {
        return true;
    }
    // 当链表长度为偶数时, 返回指向中间两个节点的前一个节点
    // 当链表长度为奇数时, 返回指向中间节点的前一个节点
    auto getPreMid = [](ListNode* head) {
        ListNode* slow = nullptr;
        ListNode* fast = head;
        while(fast && fast->next) {
            slow = slow ? slow->next : head;
            fast = fast->next->next;
        }
        return slow;
    };
    // 迭代式反转链表
    auto reverseList = [](ListNode* head) {
        ListNode* p = nullptr;
        ListNode* q = head;
        while(head) {
            q = head->next;
            head->next = p;
            p = head;
            head = q;;
        }
        return p;
    };
    ListNode* preMid = getPreMid(head);
    ListNode* headRight = preMid->next;
    preMid->next = nullptr;
    headRight = reverseList(headRight);
    ListNode* curNode = headRight;
    bool res = true;
    while(curNode && head) {
        if(curNode->val != head->val) {
            res = false;
            break;
        }
        curNode = curNode->next;
        head = head->next;
    }
    preMid->next = reverseList(headRight);
    return res;
}

21. Merge Two Sorted Lists

合并两个有序的链表，并将合并结果作为有序链表返回。

// 迭代解法
ListNode* mergeTwoLists(ListNode* p, ListNode* q) {
    // 辅助节点
    ListNode head;
    ListNode* last = &head;
    while(p && q) {
        if(p->val <= q->val) {
            last->next = p;
            p = p->next;
        }
        else {
            last->next = q;
            q = q->next;
        }
        last = last->next;
    }
    last->next = p ? p : q;
    return head.next;
}

// 递归解法
ListNode* mergeTwoLists(ListNode* p, ListNode* q) {
    if(!p) {
        return q;
    }
    if(!q) {
        return p;
    }
    ListNode* head = nullptr;
    if(p->val <= q->val) {
        head = p;
        p->next = mergeTwoLists(p->next, q);
    }
    else {
        head = q;
        q->next = mergeTwoLists(p, q->next);
    }
    return head;
}

23. Merge k Sorted Lists

给定一个由k个链表头节点所组成的数组，每个链表以升序排列。将所有链表合并为一个排序的链表，然后将其返回。

Example 1:
1
2
3
4
5
6
7
8
9
10
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

// 将这 k 个头节点交给优先级队列管理
// 优先级队列采用最小堆, 以节点内的值为排序对象
// 这样每次 pop 的时候保证总是全局所有节点中最小的节点出队
ListNode* mergeKLists(vector<ListNode*>& lists) {
    // C++ 中提供的 priority_queue 默认采用最大堆, 这里需要定制成最小堆
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
    // 所有头节点移交给 priority_queue 管理
    for(int i = 0; i < lists.size(); i++) {
        if(lists[i]) {
            pq.push(lists[i]);
        }
    }
    // 辅助节点
    ListNode head;
    ListNode* p = &head;
    while(!pq.empty()) {
        // 每次将全局最小节点入链出队
        p->next = pq.top();
        pq.pop();
        p = p->next;
        // 放进去的将是最近入链出队的节点的下一个节点
        // 这样才能保证在队列中的是全局最小的 k 个节点
        if(p->next) {
            pq.push(p->next);
        }
    }
    return head.next;
}

430. Flatten a Multilevel Doubly Linked List

给定一个双向链表，该链表除了拥有指向下一个节点和上一个节点的指针外，还具有一个孩子指针，该孩子指针可能指向也可能不指向单独的双向链接列表。这些子链表可能有一个或多个自己的子链表，依此类推，以产生一个多级数据结构，如下面的示例所示：

展平链表，以便所有节点都出现在单级双链表中。返回链表的头。

/*
// Definition for a Node.
class Node {
    int val;
    Node* prev;
    Node* next;
    Node* child;
    Node() {}
    Node(int _val, Node* _prev, Node* _next, Node* _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/

// 将题目中的孩子节点看做左孩子, 下一节点看作右孩子
Node* flatten(Node* p) {
    if(!p) {
        return p;
    }
    // 辅助节点
    Node head(0, nullptr, nullptr, nullptr);
    Node* last = &head;
    stack<Node*> s;
    s.push(p);
    while(!s.empty()) {
        Node* cur = s.top();
        s.pop();
        last->next = cur;
        cur->prev = last;
        if(cur->next) {
            s.push(cur->next);
        }
        if(cur->child) {
            s.push(cur->child);
            cur->child = nullptr;
        }
        last = last->next;
    }
    head.next->prev = nullptr;
    return head.next;
}

61. Rotate List

给定一个单链表的头节点，将链表向右旋转k个位置。

Example 1:
1
2
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Example 2:
1
2
Input: head = [0,1,2], k = 4
Output: [2,0,1]
Example 1 Example 2

// 首先要注意到:
// 1. 旋转了几次, 就会有末尾的几个节点整体次序不变的被平移到前面
// 2. 如果旋转了链表长度的倍数次, 链表将恢复原样
ListNode* rotateRight(ListNode* head, int k) {
    if(!head || k == 0) {
        return head;
    }
    ListNode* last = head;
    // 获取链表的长度, 并将 last 定位至尾节点
    int size = 1;
    while(last->next) {
        last = last->next;
        size++;
    }
    // 计算实际旋转的次数
    k = k % size;
    // 如果待旋转次数为链表长度的倍数, 不需要旋转
    if(k == 0) {
        return head;
    }
    // 计算新的头节点为第几个节点
    k = size - k;
    // 将 q 定位到新的头节点的前一个节点
    ListNode* preNewHead = head;
    while(--k > 0) {
        preNewHead = preNewHead->next;
    }
    // start 为新的头节点
    ListNode* newHead = preNewHead->next;
    // 前后接在一块即可
    preNewHead->next = nullptr;
    last->next = head;
    return newHead;
}

138. Copy List with Random Pointer

给你一个长度为n的链表，每个节点包含一个额外增加的随机指针random，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由n个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的next指针和random指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有X和Y两个节点，其中X.random --> Y。那么在复制链表中对应的两个节点x和y，同样有x.random --> y。

返回复制链表的头节点。

用一个由n个节点组成的链表来表示输入/输出中的链表。每个节点用一个[val, random_index]表示：

val：一个表示Node.val的整数。
random_index：随机指针指向的节点索引（范围从0到n - 1）；如果不指向任何节点，则为null。
你的代码只接受原链表的头节点head作为传入参数。
1
2
3
4
5
6
7
8
9
10
11
12
// Definition for a Node.
class Node {
public:
  int val;
    Node *next;
    Node *random;
    Node(int _val) {
      val = _val;
        next = NULL;
        random = NULL;
    }
 };
Example 1:
1
2
  Input: head = [[3,null],[3,0],[3,null]]
>Output: [[3,null],[3,0],[3,null]]
Example 2:
1
2
  Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
>Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

// 直接从头节点通过 next 指针, 向后一个一个遍历就可以了
// 先拷贝当前节点, 在判断当前节点的 random 指针是否为空
// 如果为空, 直接跳到下一个节点就可以了
// 如果不为空, 那就将 random 节点 new 一份
// 注意当前节点的 random 节点可能已经遍历过或者啊还没有遍历
// 1. 如果已经遍历过, 此时只需要将当前节点的拷贝节点的 random 指向它就可以了
// 那么我们怎么获取已经遍历过的节点的拷贝节点的指针呢？
// 2. 如果没有被遍历过, 直接 new 出来, 再将当前节点的拷贝节点的 random 指向它就行
// 但是, 下次通过 next 指针遍历到它的时候, 不能再 new 了, 因为它已经存在了
// 解决这个问题的方法就是借助哈希表在遍历的过程中记录当前节点和其拷贝节点之间的映射
// 这样在每次遍历新节点的时候先判断是否已经被 new 出来过了
// 下面直接看代码吧, 有详细注释
Node* copyRandomList(Node* head) {
    // 记录节点与其拷贝节点之间的映射
    unordered_map<Node*, Node*> mapping;
    // 辅助节点, 方便插入新节点和最后返回
    Node helper(0);
    // last 之后一直指向新链表的尾节点
    Node* last = &helper;
    while(head) {
        if(mapping.count(head) == 0) {
            // 如果没有, 需要重新 new 一个
            mapping[head] = new Node(head->val);
        }
        last->next = mapping[head];
        // 如果当前节点指向了一个随机节点
        // 就要为它的拷贝节点也要指向一个随机节点
        if(head->random) {
            // 如果这个随机节点没有 new 过
            if(mapping.count(head->random) == 0) {
            	mapping[head->random] = new Node(head->random->val);
            }
            last->next->random = mapping[head->random];
        }
        // 新旧链表当前节点指针同步前进一步
        head = head->next;
        last = last->next;
    }
    return helper.next;
}

// 这种解法也是建立映射, 但思路有点差别, 这里用两次 O(n) 遍历
// 第一次遍历建立所有节点到其拷贝节点的映射, 第一次遍历完所有节点都被 new 过了
// 第二次遍历将拷贝节点的 next 指针和 random 指针安置妥当
Node* copyRandomList(Node* head) {
    if(!head) {
        return nullptr;
    }
    // 建立 “原节点 -> 新节点” 的映射
    unordered_map<Node*, Node*> mapping;
    Node* cur = head;
    while(cur) {
        mapping[cur] = new Node(cur->val);
        cur = cur->next;
    }
    cur = head;
    // 构建新链表的 next 和 random 指向
    while(cur) {
        mapping[cur]->next = mapping[cur->next];
        mapping[cur]->random = mapping[cur->random];
        cur = cur->next;
    }
    // 返回新链表的头节点
    return mapping[head];
}

1019. Next Greater Node In Linked List

给出一个以头节点head作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。

每个节点都可能有下一个更大值（next larger value）：对于node_i，如果其next_larger(node_i)是node_j.val，那么就有j > i且node_j.val > node_i.val，而j是可能的选项中最小的那个。如果不存在这样的j，那么下一个更大值为0。

Example 1:
1
2
Input: [2,1,5]
Output: [5,5,0]
Example 2:
1
2
Input: [2,7,4,3,5]
Output: [7,0,5,5,0]

// 像这种下一个最大元素之类的问题, 一定用的是单调栈的技巧
// 有几道数组的题目是找下一个最大元素
// 这里给换成了链表了, 换汤不换药
// 这里主要学习的技术是链表的后序遍历
// 对的, 链表就是一种特殊的二叉树嘛
// 链表的后序遍历就是从后向前访问节点
// 你当然可以用栈来完成
// 这里用递归完成
vector<int> nextLargerNodes(ListNode* head) {
    vector<int> res;
    stack<int> s;
    function<void(ListNode*)> traverse = [&](ListNode* head) {
        if(head) {
            // 先不访问节点, 递归去下一个节点
            traverse(head->next);
            // 后序遍历代码
            // 下面代码都是是固定的单调栈算法的模板
            while(!s.empty() && s.top() <= head->val) {
                s.pop();
            }
            res.push_back(s.empty() ? 0 : s.top());
            s.push(head->val);
        }
    };
    traverse(head);
    // 最后需要反转一下
    reverse(res.begin(), res.end());
    return res;
}

148. Sort List

链表的排序。这里分别给出归并排序的递归版、迭代版以及快速排序版本。

// 归并排序, 递归解法
// T: O(nlogn), S: O(logn)
ListNode* sortList(ListNode* head) {
    if(!head || !head->next) {
        return head;
    }
    ListNode* mid = getMid(head);
    ListNode* head1 = mid->next;
    mid->next = nullptr;
    return merge(sortList(head), sortList(head1));
}

// // 这里的 bug 是如果链表的长度为 2
// // 永远返回的是指向第 2 个元素的指针
// // 对这个链表的归并排序将永远循环下去!
// // tmd 卡了我半天, 艹!
// ListNode* getMid(ListNode* head)
// {
//     ListNode* slow = head;
//     ListNode* fast = head;
//     while(fast && fast->next)
//     {
//         slow = slow->next;
//         fast = fast->next->next;
//     }
//     return slow;
// }

// 这是修正后的版本
ListNode* getMid(ListNode* head) {
    ListNode* slow = nullptr;
    ListNode* fast = head;
    while(fast && fast->next) {
        slow = slow ? slow->next : head;
        fast = fast->next->next;
    }
    return slow;
}

ListNode* merge(ListNode* p, ListNode* q) {
    ListNode helper;
    ListNode* last = &helper;
    while(p && q) {
        if(p->val < q->val) {
            last->next = p;
            p = p->next;
        }
        else {
            last->next = q;
            q = q->next;
        }
        last = last->next;
    }
    last->next = p ? p : q;
    return helper.next;
}

// 归并排序, 迭代解法
// T: O(nlogn), S: O(1)
// nextSublist 始终指向后续待归并的链表的头节点
ListNode* nextSublist = nullptr;
// tail 始终指向已经归并好的局部子链表的尾节点
ListNode* tail = nullptr;
ListNode* sortList(ListNode* head) {
    int size = 0;
    for(ListNode* temp = head; temp; temp = temp->next) {
        size++;
    }
    // 辅助头节点
    ListNode helper;
    helper.next = head;
    // 从长度为 1 开始, 每次成倍增长地归并子链表
    for(int i = 1; i < size; i *= 2) {
        ListNode* start = &helper;
        nextSublist = helper.next;
        while(nextSublist) {
            // 划出 i 个有序节点组成一个链表
            ListNode* list1 = split(nextSublist, i);
            // 再划出 i 个有序节点组成一个链表
            ListNode* list2 = split(nextSublist, i);
            // 将这划分出来的两个相邻有序链表合并
            start->next = merge(list1, list2);
            start = tail;
        }
    }
    return helper.next;
}
// 从 head 链表前面划出 size 长度的子链表出来
ListNode* split(ListNode* head, int size) {
    if(!head) {
        return head;
    }
    ListNode* p = head;
    while(--size > 0 && p) {
        p = p->next;
    }
    if(p) {
        // 这里说明 size 小于 head 链表的长度
        // 现在 p 指向被划出来链表的尾节点
        nextSublist = p->next;
        p->next = nullptr;
    }
    else {
        // 如果 size 大于 head 链表的长度
    	// 说明已经有序了
        nextSublist = nullptr;
    }
    return head;
}
// 合并两个有序链表, 和递归版本的没区别
// 主要是要更新 tail 指针
ListNode* merge(ListNode* p, ListNode* q) {
    ListNode helper;
    ListNode* last = &helper;
    while(p && q) {
        if(p->val < q->val) {
            last->next = p;
            p = p->next;
        }
        else {
            last->next = q;
            q = q->next;
        }
        last = last->next;
    }
    last->next = p ? p : q;
    // 更新 tail 指针, 使其指向这被合并完成的有序链表的尾节点
    while(last->next) {
        last = last->next;
    }
    tail = last;
    return helper.next;
}

// 快速排序版本, 最坏时间复杂度为 O(n2), 超时!
ListNode* sortList(ListNode* head) {
    // 接收一个左闭右开区间 [left, right)
    auto qs = [&] (auto&& qs, ListNode* left, ListNode* right) {
        if(left == right || left->next == right) {
            return left;
        }
        // 取首节点元素为基准值
        // 凡小于此值的节点以头插法插入到左边
        // 凡大于此值的节点以尾插法插入到右边
        ListNode* pivot = left;
        ListNode* cur = left->next;
        ListNode* tail = pivot;
        while(cur != right) {
            ListNode* temp = cur->next;
            if(cur->val < pivot->val) {
                // 头插法
                cur->next = left;
                left = cur;
            }
            else {
                // 尾插法
                tail->next = cur;
                tail = cur;
            }
            cur = temp;
        }
        // 这行很重要, tail 一直指向右边链表的尾节点
        // 要把开区间的之后的节点们接到它后面
        tail->next = right;
        // 此时, head 指向新链表的头节点
        // p 指向新链表的基准节点, 以基准节点作为右边链表的开区间尾元素进行下一次递归调用
        ListNode* newHead = qs(qs, left, pivot);
        // 跳过已经归位的基准节点
        pivot->next = qs(qs, pivot->next, right);
        return newHead;
    };
    return qs(qs, head, nullptr);
}

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

给定一个单链表L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为：L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

Constraints:

The number of nodes in the list is in the range [1, 5*10^4].

1 <= Node.val <= 1000

Example 1:
1
2
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Example 2:
1
2
Input: head = [1,2,3,4]
Output: [1,4,2,3]

// 双端队列解法
// 时间和空间复杂度均为 O(n)
void reorderList(ListNode* head) {
    deque<ListNode*> dq;
    while(head) {
        dq.push_back(head);
        head = head->next;
    }
    ListNode helper;
    ListNode* last = &helper;
    while(dq.size() > 1) {
        last->next = dq.front();
        dq.pop_front();
        last = last->next;
        last->next = dq.back();
        dq.pop_back();
        last = last->next;
    }
    if(!dq.empty()) {
        last->next = dq.front();
        last = last->next;
    }
    last->next = nullptr;
    head = helper.next;
}

// 1. 找到链表中点
// 2. 反转后半部分链表
// 3. 合并两部分链表
void reorderList(ListNode* head) {
    if(head) {
        ListNode* mid = middleNode(head);
        ListNode* q = mid->next;
        mid->next = nullptr;
        q = reverseList(q);
        mergeList(head, q);
    }
}

// 节点个数为偶数时, 返回指向中间两个节点的第二个节点
// 为奇数时返回指向中间的节点
ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

ListNode* reverseList(ListNode* head) {
    ListNode* p = nullptr;
    ListNode* q = nullptr;
    while(head) {
        q = head->next;
        head->next = p;
        p = head;
        head = q;
    }
    return p;
}

void mergeList(ListNode* p, ListNode* q) {
    ListNode* p_next = nullptr;
    ListNode* q_next = nullptr;
    while(p && q) {
        p_next = p->next;
        q_next = q->next;
        
        p->next = q;
        p = p_next;
        
        q->next = p;
        q = q_next;
    }
}

`2.24` 82. Remove Duplicates from Sorted List II

存在一个按升序排列的链表，给你这个链表的头节点head，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。

返回同样按升序排列的结果链表。

Example 1:
1
2
>Input: head = [1,2,3,3,4,4,5]
>Output: [1,2,5]
Example 2:
1
2
>Input: head = [1,1,1,2,3]
>Output: [2,3]

ListNode* deleteDuplicates(ListNode* head) {
    if(head == nullptr) {
        return head;
    }
    ListNode helper(0, head);
    ListNode* last = &helper;
    while(last->next) {
        ListNode* temp = last->next->next;
        while(temp && temp->val == last->next->val) {
            temp = temp->next;
        }
        if(temp == last->next->next) {
            last = last->next;
        }
        else {
            last->next = temp;
        }
    }
    return helper.next;
}

2.24 82. Remove Duplicates from Sorted List II

`2.24` 82. Remove Duplicates from Sorted List II