指针使用前，一定要检查指针是否是nullptr。
善用dummyNode
链表操作三板斧：slice, transform, splice 裁剪，变换，拼接
裁剪下来的节点，一定要设置next为nullptr。

链表逆序：
LC206 Reverse Linked List
⚠️LC92 Reverse Linked List II[用dummyHead更容易处理m == 0的情况]
链表删除：
LC237 Delete Node in a Linked List[靠拷贝后一个节点的val来做删除]
LC19 Remove Nth Node From End of List[无论如何也要遍历，裁拼]
LC203 Remove Linked List Elements[删除给定值的节点，裁拼]
LC83 删除排序链表中的重复元素[裁变拼]
⚠️LC82 删除排序链表中的重复元素II[要求将重复元素全部清除，需要维护两个指针]
链表求环：
LC141 Linked List Cycle
LC142 Linked List Cycle II[环长为相遇时慢指针移动的步数]
LC287 Find the Duplicate Number[相等的是first/slow，返回的也是first/slow]
链表归并/排序：
LC21 Merge Two Sorted Lists
LC23 Merge k Sorted Lists
LC147 对链表进行插入排序
⚠️⚠️LC148 排序链表
其他：
❌LC24 两两交换链表中的节点
❌LC143 重排链表
 LC138 复杂链表复制
 LC725 分隔链表
 LC160 两个链表的公共节点
❌LC24 K个一组翻转链表
 LC1171 从链表中删去总和为零的连续节点
 LC430 扁平化多级双向链表

STL中的链表

C++11 起有官方提供的单向链表了(forward_list)
STL中的list，提供以下的成员函数(member function)
- 排序(sort)
- 归并(merge)
- 移除(remove/ remove_if) 和类似移除的函数(unique)
  <algorithm>里面提供的非成员函数的remove只会把不想要的元素给挪动到容器的尾部，并返回一个指向逻辑结尾的迭代器。
  
  通过以满足不移除的元素出现在范围起始的方式，迁移（以移动赋值的方式）范围中的元素进行移除。保持剩余元素的相对顺序，且不更改容器的物理大小。指向范围的新逻辑结尾和物理结尾之间元素的迭代器仍然可解引用，但元素自身拥有未指定值（因为可移动赋值 (MoveAssignable) 的后置条件）。调用 remove 典型地后随调用容器的 erase 方法，它擦除未指定值并减小容器的物理大小，以匹配其新的逻辑大小。
  和<algorithm>里提供不同，list自己提供的remove会切切实实的把不想要的元素给删掉。
  
  参考
  - cppreference.com: std::list::remove
  - Effective STL, Scott Meyer, Item 44 Prefer member functions to algorithms with the same names.
  - Effective STL, Scott Meyer, Item 32 Following remove-like algorithms by erase if you really want to remove them.
  - Wikipedia: Erase-remove idiom
不同STL中list的实现和哨兵节点(sentinel)
TODO

删除节点问题

任何在这种暴露元素指针的容器里，直接通过指针来删除元素的方法都可能导致未定义行为。这些题就只是做做而已。对于释放申请来的内存的问题，一定要谨慎。尽量用智能指针。这个题目可以练习自己实现一个包裹的很好的链表LC707 Design Linked List

O(1)时间删除链表的一个给定节点

LC237 Delete Node in a Linked List

这个题目限定了：链表里至少有两个元素且被删除的元素不是末尾元素。为什么会有这样的限定？我们可以从AcWing28 在O(1)时间删除链表结点这个错误的题目看出来，并在剑指Offer 18来解决这个问题。

这个题目只提供了链表中要被删除的那个节点的指针。因为是单向链表，我们无法获取这个节点的前一个节点的指针，也就无法更改他前一个节点的next。一个简单的想法是，把当前节点的下一个节点的值拷给当前节点，然后再把当前节点next设置成下一个节点的next，最后不要忘了删除下一个节点。

这种复制数值的删除链表方法，仅适用于val的复制代价很小的情况，比如整个类的实现都被放在了一个指向其实现的指针的情况，即pImpl idiom 。详见cppreference: pImpl.

code

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val; //不需要判断：这个节点是空节点？
        auto tmp = node->next->next; //不需要判断：这个节点的下一个节点是空节点？
        delete node->next;
        node->next= tmp;        
    }
};

【错误的题目】AcWing28 在O(1)时间删除链表结点错在：这个题目没有提供头节点

这个题目没有任何限定，所以

这个链表可能为空(!node)：什么都不做直接返回就可以了
这个节点可能是最后一个节点(!(node->next)，或链表只有一个节点)：把这个节点删除

最后两个特殊情况会导致未定义行为(undefined behavior)。因为如果一旦删除头节点，头节点的指针指向的就是被释放的内存。同理，如果删除尾节点，尾节点的前一个节点的指针也将指向一块被释放的内存。如果像链表设计惯例里一样添加一个【哨兵节点】，会减少很多麻烦。

【错误的程序】但能AC

class Solution {
public:
    void deleteNode(ListNode* node) {
        if(!node) return;
        if(!node->next){
            delete node;
            node = nullptr;
            return;
        }
        node->val = node->next->val;
        auto tmp = node->next;
        node->next = node->next->next;
        delete tmp;
    }
};

剑指Offer 18

这个题目类似前面的AcWing28 在O(1)时间删除链表结点，但是提供了链表头节点的指针的指针。这个链表头节点可以用来解决被删节点是最后一个节点的问题。

code

class Solution {
public:
    void deleteNode(ListNode** ppHead, ListNode* node) {
    	//如果链表为空或者被删除节点为空
        if(!ppHead||!(*ppHead)||!node) return;
        //如果删除头节点
        if(node == *ppHead){
            delete node;
            //这句话不需要了，因为node在return时就被销毁了。
            //node = nullptr 
            return;
        }
        //如果删除的非尾节点
        if(node->next){
	        node->val = node->next->val;
	        auto tmp = node->next;
	        node->next = node->next->next;
	        delete tmp;
        }
        //如果删除尾节点
        else//!(node->next)
        {	
	        auto pBeforeNode = *pHead;
		    while(pBeforeNode->next != node) 
		        pBeforeNode = pBeforeNode->next;
		    delete node;
		    //这句话不需要了，因为node在return时就被销毁了。
		    //node = nullptr 
		    pBeforeNode->next = nullptr;
        }
    }
};

删除链表中所有有给定值的节点

LC203 Remove Linked List Elements
因为无论如何都要遍历链表，所以即使所有删除都是O(1)也不会使算法复杂度有所减少。所以按照处理链表的一般思路：

- 从头上取下来一个节点
- 判断这个节点的val是不是等与val
    - 如果是就不拼接
    - 如果不是就给他拼到新链表上

code

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        auto dummy = ListNode{INT_MIN};
        auto np = &dummy;

        while(head)
        {
            // backup
            auto next = head->next;

            // slice
            head->next = nullptr;

            // splice
            if(head->val != val)
            {
                np->next = head;
                np = np->next;
            }

            // forward
            head = next;
        }

        return dummy.next;
    }
};

删除链表中倒数第k个节点

LC19 Remove Nth Node From End of List
【这是一个有问题的题目】
思路：

怎么得到要删除节点的前一个节点？
如果想要删除单链表中的一个节点，那我们必须得有这个节点的前驱。
如何一次遍历就得到一个节点的前驱？弄个beforeNode，每次node = node->next之前，都把node赋值给beforeNode，这样beforeNode就一直是node前一个节点的指针了。同时还要注意beforeNode要初始化成(ListNode*)nullptr，这样我们就可以根据它是不是nullptr来判断node是不是头节点了。
怎么一次遍历找到倒数第k个节点
先让head往前移动k个位置，之后再让head和nthNode一起往前移动，直到head移动到末尾(nullptr)。此时的nthNode就是倒数第k个节点了。

code

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto p = head;
        while(--n)
        {
            head = head->next;
        }

        auto dummy = ListNode{INT_MAX};
        auto np = &dummy;

        while(head && head->next)
        {
            // backup
            auto next = p->next;
            auto hnext = head->next;
            // slice
            p->next = nullptr;
            // splice
            np->next = p;
            // forward
            np = np->next;
            p  = next;
            head = hnext;
        }

        p = p->next;

        while(p)
        {
            auto next = p->next;
            p->next = nullptr;
            np->next = p;
            np = np->next;
            p = next;
        }

        return dummy.next;
    }
};

反转链表

反转整个链表

剑指Offer 24, LC206 Reverse Linked List
特殊情况：

head == nullptr

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

反转部分链表

LC92 Reverse Linked List II
思路：
如果我们逆序的链表的一部分，那么我们就得获得这个链表m前面那个节点和n后面那个节点的指针。这样逆序之后我们才好链接。
如果逆序的是第一个节点，即m==0，那就让m前面那个节点设置成nullptr即可。以后判断的时候可以用。

特殊情况：

head == nullptr
m == 0
m == n

特殊情况当中m == 0非常讨厌。为了必然这种情况发生，还是采用dummyHead的方式，简单好写。
另一个让人特别的迷糊的地方就是逆序后链表哪里是头，哪里是尾：

                                       reverse_last
                                             ^
                           reverse           |
     +-+-+-+-+-+  +-+-----          +-+-+-+-+++  +-+-----
     | | | | | |  | |      +------> | | | | | |  | |
     +++-+-+-+++  +++-----          +++-+-+-+-+  +++-----
      ^       ^    ^                 ^            ^
      |       |    |                 |            |
      +       +    +                 +            +
reverse_last ptr head               ptr         head

...

// 逆序之前将链表头保存在起来。
// 逆序之后reverse_last所指之处即为链表尾
auto reverse_last = head;
// 逆序之后,ptr所指之处即为逆序后的链表头
// 逆序之后,head 所指之处为原来链表中，在被逆序的序列之后的第一个节点。
ListNode* ptr = nullptr;
cnt = n - m + 1;
while(cnt)
{
    auto next = head->next;
    head->next = ptr;
    ptr = head;
    head = next;
    --cnt;
}

...

code

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        auto dummy = ListNode{INT_MAX};
        auto p = &dummy;

        for(int i = 0; i < m - 1; ++i)
        {
            // backup
            auto next = head->next;
            // slice
            auto cur = head;
            cur->next = nullptr;
            // splice
            p->next = cur;
            // move forward
            p = p->next;
            head = next;
        }

        // now p is at the end of the first part
        // head is at the beginning of the reverse part
        auto r_tail = head;
        ListNode* r_head = nullptr;
        auto cnt = n - m + 1;
        while(cnt--)
        {
            //backup
            auto next = head->next;
            // slice
            auto cur = head;
            cur->next = nullptr;
            // splice
            cur->next = r_head;
            // move forward
            r_head = cur;
            head = next;
        }
        // now head is at the beginning of part 3
        // splice r_tail with head
        r_tail->next = head;
        // splice p with r_head
        p->next = r_head;

        return dummy.next; 
    }
};

回文链表

LC234 Palindrome Linked List
题目要求用$O(n)$的时间复杂度和$O(1)$的空间复杂度来判断一个单向链表是否是回文的。
思路：

先遍历一次链表，找到链表长度l。
如果l是奇数，我们就从l/2 + 1的位置开始给链表逆序（index 从 0开始）(因为121也是回文！)。如果l是偶数，就从l/2的位置开始给链表逆序。
逆序之后我们比较两个链表是否相同就可以了。
这会修改原始链表！

下面的代码修改了原始链表，而且并没有帮忙改回去。

code

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head) return true; 
        if(!head->next) return true;        
        size_t len = 0;
        auto lhead = head;
        auto rhead = head;
        while(head){
            ++len;
            head = head->next;
        }        
        if(len & 1) len = len / 2 + 1;
        else        len = len / 2;        
        while(len){
            --len;
            rhead = rhead->next;
        }       
        auto rhead2 = rhead;
        auto tmp = (ListNode*)nullptr;        
        while(rhead2){
            auto next = rhead2->next;
            rhead2->next = tmp;
            tmp = rhead2;
            rhead2 = next;
        }        
        rhead = tmp;        
        while(lhead && rhead){
            if(lhead->val != rhead->val) return false;
            lhead = lhead->next;
            rhead = rhead->next;
        }     
        //resume the linked list is not required in this problem.    
        return true;
    }
};

旋转链表

LC61 Rotate List
高级版的链表的倒数第k个节点。先遍历链表找到链表的长度。然后用n = k mod len，之后从倒数的第n位开始给链表裁下来放在前面即可。

code

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head) return nullptr;
        size_t len = 0;
        auto end = head;
        while(end){
            end = end->next;
            ++len;
        }
        auto num = k % len; 
        if(num == 0) return head;        
        auto last = head;
        auto pre_rk = head;
        while(num){
            --num;
            last = last->next;
        }    
        while(last->next){
            last = last->next;
            pre_rk = pre_rk->next;
        }    
        auto rk = pre_rk->next;
        pre_rk->next = nullptr;
        last->next = head;
        return rk;        
    }
};

链表的环

找出链表的环

剑指Offer 23, LC141 Linked List Cycle, LC142 Linked List Cycle II

目标：

判断链表是否有环
确定环的长度
确定环的入口节点

剑指Offer 23中给出了用快慢指针来判断是否有环的方法。但其确定环的长度和入口节点的方法太复杂。这里我们给出一种更简单的方法，用来确定入口节点和环长。

使用两个指针，一个指针一次移动一步，另一个指针一次移动两步
不断向前移动两个指针，直到
- 两个指针相遇
- 快指针移动到了nullptr $\rightarrow$ 证明链表无环。
相遇的时候，慢指针移动的步数就是环长。不需要像《剑指Offer》里面一样再用两个指针来计数。
从【相遇的节点】和【链表头】各自出发一个指针，每次向前移动一个节点，直到两个指针相遇。这个指针就是链表的头入口。

证明算法的正确性：

证明相交的时间刚好是环的长度:
假设链表存在环。设链表的环的入口节点是第$n$个节点，环中最后一个节点（也是环中环入口节点前一个节点）为$m$。必然有$m > n$。设快节点速度为$2$，慢节点速度为$1$。快节点进入环的时间是$\frac{n}{2}$，快节点到环中最后一个节点的时间是$\frac{m}{2}$。之后在$[\frac{m}{2}, \frac{m}{2}+\frac{m-n}{2})$时间内，快节点的位置满足方程$P_f = n+2(t - \frac{m}{2}) = 2t+n-m$。慢节点的坐标满足方程$P_s = t$。假设在$[\frac{m}{2}, \frac{m}{2}+\frac{m-n}{2})]$能相交，求交点得相交时间为$\frac{m}{2}< m-n < \frac{m}{2}+\frac{m-n}{2}$，因此的确在此时间段内相交。相交的时间刚好是环的长度。

注意在实现这个算法的时候有一些小细节：

- 建议用一个while(true)并其中用流程控制跳出，如果在while的括号里判断就会出现一些很诡异的BUG，原因未知。而且如果你想在while的括号里判断，就得让两个指针初始化成不一样的（`fast=head->next, slow = head`），在循环开始前又得判断一次fast是不是空指针，很麻烦。

code

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

code

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head || !head->next) return nullptr;
        auto fast = head;
        auto slow = head;
        while(true){
            slow = slow->next;
            fast = fast->next;
            if(fast == nullptr) return nullptr;
            fast = fast->next;
            if(fast == nullptr) return nullptr;
            if(fast == slow) break;
        }      
        slow = head;       
        while(fast != slow){
            fast = fast->next;
            slow = slow->next;
        }       
        return slow;    
    }
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head || !head->next) return nullptr;
        auto fast = head;
        auto slow = head;
        while(true)
        {
            fast = fast->next;
            slow = slow->next;
            if(!fast) return nullptr;
            fast = fast->next;
            if(!fast) return nullptr;
            if(fast == slow) break;
        }

        while(true)
        {
            if(head == slow) return head;
            head = head->next;
            slow = slow->next;  
        }

        return nullptr;
    }
};

数组中重复的数字

LC287 Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

这个题可以被转化成链表求环问题。如果$n+1$个数字，每个数组的取值范围都是$[1, n]$，根据抽屉原理，必然有两个数字是相同的。我们把每一个数组的元素看作链表的一个node，而数组里存放的数组看作是next，我们就得到了一个有环的链表（有两个next是相同的）。我们用上面链表求环的方法就可以在$O(n)$的时间复杂度和$O(1)$的空间复杂度下完成这个问题了。

code

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        
        int slow = 0;
        int fast = 0;
        
        while(true){
            slow = nums[slow];
            fast = nums[fast];
            fast = nums[fast];
            
            if(slow == fast) break;
        }
        slow = 0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        } 
        return slow;
        
    }
};

两个链表的公共节点

LC160 Intersection of Two Linked Lists

如果两个链表一样长的话，直接让指针在链表头处一起向前移动，直到相等，就找到了公共节点了。可惜这个题两个链表不一定是一样长的。但我们可以通过遍历两个链表，得到长度差，让长链表指针先走。这样就变成了”一样长”的链表了。

思路

首先我们得获得两个链表的长度lenA和lenB
计算两个链表的长度差adv = abs(lenA - lenB)
再分别从两个链表头处开始，让长链表的头指针先走adv

再让两个指针一起往前走，直到【相等】或者一个出现【nullptr】。

code

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return nullptr;
        auto pHeadA = headA;
        auto pHeadB = headB;
        
        size_t lenA = 0;
        size_t lenB = 0;
        while(headA && headB){
            headA = headA->next;
            headB = headB->next;
            ++lenA;
            ++lenB;
        }
        
        while(headA){
            headA = headA->next;
            ++lenA;
        }
        
        while(headB){
            headB = headB->next;
            ++lenB;
        }
        
        auto _getIntersection = [](ListNode* pHeadA, ListNode* pHeadB, size_t adv){ 
            while(adv){
                pHeadA = pHeadA->next;
                --adv;
            }

            while(pHeadA && pHeadB){
                if(pHeadA == pHeadB) return pHeadA;
                pHeadA = pHeadA->next;
                pHeadB = pHeadB->next;
            }
            return (ListNode*)nullptr; 
        };
        
        if(lenA > lenB) return _getIntersection(pHeadA, pHeadB, lenA - lenB);
        else            return _getIntersection(pHeadB, pHeadA, lenB - lenA); 
    } 
};

链表排序

合并2个排序的链表

LC21 Merge Two Sorted Lists
该题目为归并(merge)的实现。见”排序”。

注意：

链表的归并过程不需要置裁剪下来的节点next指针为nullptr，因为这里不涉及到链表倒置。
当一个链表到头之后，不需要再用while循环来拼接另一个链表。只需要接上即可。

code更清新的版本

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        auto DummyHead = ListNode{INT_MIN};
        auto ptr = &DummyHead;

        while(l1 && l2)
        {
            if (l1->val < l2->val)
            {
                ptr->next = l1;
                l1 = l1->next;
            }
            else
            {
                ptr->next = l2;
                l2 = l2->next;
            }
            ptr = ptr->next;
        }

        if(l1)
        {
            ptr->next = l1;
        }

        if(l2)
        {
            ptr->next = l2;
        }

        return DummyHead.next;
    }
};

slice-splice 版本

void slice_append(ListNode** pl2, ListNode** pp)
{
    auto& l2 = *pl2;
    auto& p = *pp;
    //backup 
    auto next = l2->next;
    //slice
    l2->next = nullptr;
    //splice
    p->next = l2;
    //forward
    l2 = next;
    p = p->next;
}
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        auto dummy = ListNode{INT_MAX};
        auto p = &dummy;

        while(l1 && l2)
        {
            if(l2->val < l1->val)
            {
                slice_append(&l2, &p);
            }
            else
            {
                slice_append(&l1, &p);
            }
        }

        if(l1)
        {
            p->next = l1;
        }
        else if(l2)
        {
            p->next = l2;
        }

        return dummy.next;
    }
};

合并k个排序的链表

LC23 Merge k Sorted Lists
该题目为k路归并(merge sort)的实现。见”排序”。

注意的问题：

测试用例很恶心，有空的链表头指针。如果不事先把这些东西remove-erase掉，就会导致在比较器里解引用空指针。当然另一个解决办法是在比较器中判断是不是空指针。由于比较器是要被调用最频繁的函数，在其中引入流程控制就会大大降低效率。不如直接线性搜索去掉空指针。
同时也是空指针的问题，注意push()进入队列的也不能是空指针，否则也会引起上面的问题。但是在这里引入一个判断，对整体的效率影响不大。
priority_queue的构造函数除非是传iterator来构造的版本，第一个参数都是自定义比较器。而且应该将lists移动到pq中构造，避免复制。
一定要先记录top()然后尽早pop()，如果push()了新节点之后再pop()，可能会把刚push()进来的节点pop()出去，导致BUG。

code

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        lists.erase(remove(lists.begin(), lists.end(), nullptr), lists.end());
        auto dummy = ListNode{INT_MAX};
        auto p = &dummy;
        auto cmp = [](auto lhs, auto rhs)
        {
            return lhs->val > rhs->val;
        };
        auto pq = priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)>{cmp, std::move(lists)};

        while(!pq.empty())
        {
            auto node = pq.top();
            pq.pop();
            // slice
            auto next = node->next;
            node->next = nullptr;
            // splice
            p->next = node;
            // forward
            p = p->next;

            if(next)
            {
                pq.push(next);
            }
        }

        return dummy.next;
    }
};

链表插入排序

LC147 对链表进行插入排序

仍然按照裁剪、变换、拼接的方式进行，需要注意的是这次拼接的位置不再是新链表的尾部。而是要对新链表进行线性查找，找到第一个比当前node大的node(greater)，和greater前面一个node(before)。一些边界条件：

- greater可能是`nullptr`：这个无所谓，因为只会把greater拼在node后面
- before是`nullptr`：也就是说第一个比当前node大的node是新链表头，我们只需将这个node的next设置为当前链表头，并返回新链表头即可。

code

void insert(ListNode* pos, ListNode* node)
{
    auto next = pos->next;
    pos->next = node;
    node->next = next;
}
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        auto dummy = ListNode{INT_MIN};
        auto p = &dummy;

        while(head)
        {
            // backup
            auto next = head->next;
            // slice
            head->next = nullptr;
            // splice
            auto p1 = p;
            auto p2 = dummy.next;
            while(p2 && head->val > p2->val)
            {
                p1 = p1->next;
                p2 = p2->next;
            }

            insert(p1, head);

            //forward
            head = next;
        }

        return dummy.next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        auto dummy = ListNode{INT_MIN};
        auto ptr = &dummy;

        while(head)
        {
            // slice
            auto next = head->next;
            head->next = nullptr;
            // splice
            ptr = insert(ptr, head);
            // move on
            head = next;
        }

        return dummy.next;
    }

    ListNode* insert(ListNode* head, ListNode* node)
    {
        // we have to find the first node
        // (and the node before that node) 
        // that is greater than the given node

        ListNode* before = nullptr;
        auto greater = head;

        while(greater && !(node->val < greater->val))
        {
            before = greater;
            greater = greater->next;
        }
        if(before) before->next = node;
        node->next = greater;     

        // return the new head
        if(!before) return node;
        return head;  
    }
};

链表归并排序

LC148 排序链表

采用自低向上的归并排序，时间复杂度O(NlogN)，不需要额外空间。

思路：

写一个merge方法，可以merge任意长度的两个链表，即LC21 Merge Two Sorted Lists。
写一个cut(ListNode* head, size_t len)方法，将从head开始的，长度为len的链表从原链表上裁剪下来。返回被裁剪后的原链表头指针。如果len大于原链表的长度，返回nullptr。这里注意一定别忘了把被裁下那一段的尾节点的next指针置空。
遍历链表，找出链表的长度len
维护一个裁剪长度变量，初始化为cutLen = 1
- 初始化一个dummyHead，用来连接从原链表上被裁下来的链表。这里为了方便，要把这个哑节点的next设置为head。
- 初始化cur指针为链表头指针
- 从left = cur处，裁剪一个长度为cutLen的链表，得到剩余链表的头指针right
- 从right处，再裁减一个长度为cutLen的链表，将返回的剩余链表的头指针赋值给cur
- 归并left和right两个链表，将返回的链表头的指针赋值给dummyHead->next
- 更新dummyHead为其后面所连接的链表的尾节点指针
- 重复上述步骤直到cur为空指针
更新cutLen = cutLen * 2
重复上述步骤直到cutLen >= len

Jul/14/2020 可以省略第一次对链表的遍历。当从链表上cut下来的第一段就导致cur指针变为nullptr时，就自然有cutLen >= len了。

Feb/18/2020 重新写了一次sortList，但是debug了好久好久

链表的TLE不一定是因为你程序中有死循环，还可能是因为你的链表出环了
错误点1: mergeList里面的主循环忘记更新指针end = end->next
错误点2: sortList里面的外层循环，忘记了重置指针end = &dummy
- 能让他称为局部变量的就尽量写成局部变量，这样就不会忘记更新了

Jul/14/2020 code

auto slice_front(ListNode* head, size_t n)
{
    for(size_t i{1}; i < n && head; ++i)
    {
        head = head->next;
    }

    if(head)
    {
        auto next = head->next;
        head->next = nullptr;
        return next;
    }
    else
    {
        return head;
    }
}

auto slice_append(ListNode*& l2, ListNode*& p)
{
    // backup
    auto next = l2->next;
    // slice
    l2->next = nullptr;
    // splice
    p->next = l2;
    // forward
    l2 = next;
    p = p->next;
}

auto merge_list(ListNode* l1, ListNode* l2)
{
    auto dummy = ListNode{INT_MIN};
    auto p = &dummy;

    while(l1 && l2)
    {
        if(l2->val < l1->val)
        {
            slice_append(l2, p);
        }
        else
        {
            slice_append(l1, p);
        }
    }

    while(l1)
    {
        slice_append(l1, p);
    }

    while(l2)
    {
        slice_append(l2, p);
    }

    return make_pair(dummy.next, p);
}

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        
        if(!head || !head->next)
        {
            return head;
        }

        auto dummy = ListNode{INT_MIN};
        dummy.next = head;

        for(size_t len{1};; len *= 2)
        {
            auto cur = dummy.next;
            auto p = &dummy;
            while(cur)
            {
                // slice the first part
                auto first_head = cur;
                cur = slice_front(cur, len);
                // if the first_head is dummy.next and cur is nullptr,
                // then we do not need to continue
                if(first_head == dummy.next && !cur)
                {
                    return first_head;
                }
                // slice the second part
                auto second_head = cur;
                cur = slice_front(cur, len);
                // merge them together
                auto [merge_head, merge_tail] 
                    = merge_list(first_head, second_head);
                // append them to the dummy head.
                p->next = merge_head;
                p = merge_tail;
            }            
        }
    }
};

Feb/18/2020 code

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // count the size of the list
        int size = 0;
        auto cntPtr = head;
        while(cntPtr)
        {
            ++size;
            cntPtr = cntPtr->next;
        }

        if(size < 2) return head;
        // set up dummyHead
        auto dummy = ListNode{INT_MIN};
        auto end   = &dummy;

        // bottom-up mergesort
        int cut_size = 1;
        while(cut_size < size)
        {
            while(head)
            {
                // cut the first piece
                auto first_head = head;
                head = cutList(head, cut_size);
                // cut the second piece
                auto second_head = head;
                head = cutList(head, cut_size);
                // merge them together
                auto [merge_head, merge_end] = mergeList(first_head, second_head);
                // append the list
                end->next = merge_head;
                end = merge_end;
            }
            head = dummy.next;
            end = &dummy;
            cut_size *= 2;
        }

        return dummy.next;
    }
    // cut a sublist of size n in out of the beginning of 
    // head, return the head of the remaining part.
    ListNode* cutList(ListNode* head, int n)
    {
        --n;
        ListNode* ptr = head;
        while(ptr && n)
        {
            ptr = ptr->next;
            --n;
        }
        // not enough node to cut
        if(!ptr) return nullptr;
        // cut 
        auto next = ptr->next;
        ptr->next = nullptr;
        return next;
    }

    pair<ListNode*, ListNode*> mergeList(ListNode* h1, ListNode* h2)
    {
        auto dummy = ListNode{INT_MIN};
        auto end   = &dummy;
        while(h1 && h2)
        {
            if(h2->val < h1->val)
            {
                end->next = h2;
                h2 = h2->next;
            }
            else
            {
                end->next = h1;
                h1 = h1->next;
            }

            end = end->next;
        }

        if(h1)
        {
            end->next = h1;
        }

        if(h2)
        {
            end->next = h2;
        }

        while(end->next)
        {
            end = end->next;
        }

        end->next = nullptr;

        return {dummy.next, end};
    }
};

Feb/9/2020 code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) 
    {
        int len = 0;
        auto ptr = head;
        auto dummyNode = ListNode{INT_MIN};
        dummyNode.next = head;
        //we need to know the length of the list
        while(ptr)
        {
            ptr = ptr->next;
            ++len;
        }

        int cutLen = 1;
        while(cutLen < len)
        {
            ptr = dummyNode.next;
            auto pDummyNode = &dummyNode;
            while(ptr)
            {
                auto left  = ptr;
                auto right = cut(left, cutLen);
                ptr = cut(right, cutLen);

                pDummyNode->next = mergeList(left, right);
                while(pDummyNode->next)
                {
                    pDummyNode = pDummyNode->next;
                }
                                
            }
            cutLen *= 2;
        }
        return dummyNode.next;
    }

    ListNode* cut(ListNode* head, int len)
    {
        --len;
        // move to the end of the linked list 
        // that has length == len
        while(len && head)
        {
            head = head->next;
            --len;
        }

        // not enough nodes, return nullptr.
        if(!head) return nullptr;
        
        auto newHead = head->next;
        // DO NOT FORGET TO CUT!
        // cut the connection between this linked list and the reminder
        head->next = nullptr;
        return newHead;
    }

    ListNode* mergeList(ListNode* l1, ListNode* l2)
    {
        ListNode dummyNode = ListNode{INT_MIN};
        auto ptr = &dummyNode;
        while(l1 && l2)
        {
            if (l1->val < l2->val)
            {
                ptr->next = l1;
                l1 = l1->next;
            }
            else
            {
                ptr->next = l2;
                l2 = l2->next;
            }

            ptr = ptr->next;
        }

        if(l1)
        {
            ptr->next = l1;
        }
        if(l2)
        {
            ptr->next = l2;
        }

        return dummyNode.next;
    }
};

复杂链表的复制

LC138 Copy List with Random Pointer，剑指Offer 35

使用hashmap的解法

遍历链表，将链表中的node复制一份并记录下新的地址。以node原来的地址为Key, 新的地址为value存在hashmap当中。注意：nullptr的不用存，因为也不用对应。
这次遍历的过程中，还要注意保存一下每次新建的node的地址到下一个循环。重置这个地址的node的next指针到下一个新建的node。
再遍历新的链表，设置random指针的值。方法就是用原来的random当Key从hashmap当中找新的random即可。

使用dummyNode，减少循环内的流程控制语句，可以显著提升效率。

code

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> map{};
        Node copyHead = Node{INT_MIN};
        auto pCopyHead = &copyHead;
        // build the new linked list
        while(head)
        {
            pCopyHead->next = new Node{head->val};
            pCopyHead->next->random = head->random;
            // set up the mapping
            map[head] = pCopyHead->next;
            head = head->next;
            pCopyHead = pCopyHead->next;
        }

        // iterate throught the new linked list
        // fix the random pointer
        pCopyHead = &copyHead;
        pCopyHead = pCopyHead->next;
        while(pCopyHead)
        {
            pCopyHead->random = map[pCopyHead->random];
            pCopyHead = pCopyHead->next;
        }

        return copyHead.next;
        
    }
};

旧LeetCode的Node API

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> nodeMap;
        auto copiedHead = head;
        auto nodeCopied = new Node(INT_MIN, nullptr, nullptr);
        auto nodeCopied2 = nodeCopied;
        while(head){
            nodeCopied->next = new Node(head->val, nullptr, head->random);
            nodeCopied = nodeCopied->next;
            nodeMap[head] = nodeCopied; 
            head = head->next;
        }
        for(auto& pair : nodeMap){
            if(pair.second->random)
                pair.second->random = nodeMap[pair.second->random];
        }
        delete nodeCopied2;
        return nodeMap[copiedHead];
    }
};

这是一个没用使用hashmap，而是采用排序数组上二分查找的实现，仅仅是为了练习而写（不推荐）

class Solution {
public:
    Node* copyRandomList(Node* head) {
        using pNodePair = std::pair<Node*, Node*>;
        Node* tmpHead = head;
        std::vector<pNodePair> vpNodePair;
        while(head){
            vpNodePair.emplace_back(head,new Node(head->val,nullptr,nullptr));
            head = head->next;
        }
        
        std::sort(vpNodePair.begin(),vpNodePair.end(),[](const pNodePair& lhs, const pNodePair& rhs ){
            return std::less<Node*>()(lhs.first,rhs.first);
        });
        
        auto compare = [](const pNodePair& lhs, Node* rhs){
            return std::less<Node*>()(lhs.first,rhs);
            };
        
        auto findCorrespondingNode = [&vpNodePair,&compare](Node* what){
            return what == nullptr ? nullptr : std::lower_bound(vpNodePair.begin(),vpNodePair.end(),what,compare)->second;};
        
        std::for_each(vpNodePair.begin(),vpNodePair.end(),[&vpNodePair,&findCorrespondingNode](const pNodePair& pair){
            pair.second->next = findCorrespondingNode(pair.first->next);
            pair.second->random = findCorrespondingNode(pair.first->random);
        });
        
        return findCorrespondingNode(tmpHead);
    }
};

空间复杂度为O(1)的解法

解法来自《剑指Offer》面试题35

思路：
把每一个复制后的node先放在原来的node之后。这样找random的时候，直接找random->next即可。

先遍历一次链表，在每一个node之后都加入一份该node的拷贝。
再遍历一次链表，把拷贝的node的random修改为random->next。
再遍历一次链表，把两个链表分离开。

code

class Solution {
public:
    Node* copyRandomList(Node* head) {
        
        if(!head) return head;
        
        auto ddHead = head;
        auto copyHead = head;
        auto newHead = head;
        
        while(head){
            auto nextNode = head->next;
            head->next = new Node(head->val, nextNode, head->random);
            head = nextNode;
        }        
        while(newHead){
            newHead = newHead->next;
            if(newHead->random)
                newHead->random = newHead->random->next;
            newHead = newHead->next;
        }       
        
        auto finalHead = copyHead->next;     
        while(copyHead){
            auto nodeCopied = copyHead->next;
            if(nodeCopied)
                copyHead->next = nodeCopied ->next;
            copyHead = nodeCopied;
        }
        return finalHead;  
    }
};

删除排序链表中的重复元素

LC83 删除排序链表中的重复元素, LC82 删除排序链表中的重复元素II

LC83的思路也是操作链表的一般思路，即取下、处理、拼接。需要注意的细节：

- 处理之前别忘备份一份`next`
- 处理之后一定要把`next`置空
- 拼接之后要移动到末尾

code

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        auto dummy = ListNode{INT_MIN};
        auto np = &dummy;

        while(head)
        {
            // backup
            auto next = head->next;

            // slice
            head->next = nullptr;

            // splice

            if(head->val != np->val)
            {
                np->next = head;
                np = np->next;
            }

            head = next;
        }

        return dummy.next;
    }
};

LC82的思路：因为要求删掉有重复的Node，所以不能简单的像前一题一样，判断和新链表末尾的元素是否相同。

维护两个指针l和r，不变式为r >= l且l总为链表头
初始化l 和 r 为head和head->next
检查l和r
- 如果l不是空指针，但r是空指针。这说明l所指的node已经是链表中最后一个node了。我们直接把l裁减拼接即可。
- 如果不相等，就把l对应的node裁减，拼接到新链表尾。
- 如果相等，就向右移动r直到l和r不相等
  - 注意如果r == nullptr(被移动到了链表尾部)，为了维持不变式，需要设置l == nullptr
向前移动l和r

Feb/18/2020更新：

我们总是保证r在l前面，这一点体现将l从链表中拿下接到新链表之后。l和r都要向前一步。
如果在检查l和r相等的分支中，r移动到了链表末尾，我们可以直接break循环，因为此时l到r之间全为重复节点。

code

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        auto dummy = ListNode{INT_MIN};
        auto p = &dummy;

        while(head)
        {
            auto l = head;
            auto r = head->next;
            // dupicate
            while(r && l->val == r->val)
            {
                r = r->next;
            }
            
            // duplicate if r was moved.
            if(r != l->next)
            {
                head = r;
                continue;
            }

            // backup 
            auto next = head->next;
            // slice
            auto cur = head;
            cur->next = nullptr;
            // splice
            p->next = cur;
            // forward
            head = next;
            p = p->next;
        }

        return dummy.next;
    }
};

Feb/18/2020-code

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
        auto dummy = ListNode{INT_MIN};
        auto end   = &dummy;

        auto l = head;
        auto r = head->next;

        while(l)
        {
            // check if l and r are the same
            // if so, we have to move r unitl they 
            // are not same
            if(r && l->val == r->val)
            {
                while(r && l->val == r->val)
                {
                    r = r->next;
                }
            
                // if r moves to the end, then all duplicates
                // between l and r, we could break the loop
                if(!r) break; 
                // move l to r
                l = r;
                // move r to r->next;
                r = r->next;
                // back to top and check again
                continue;
            }
            // l->val != r->val, we could append l onto the list
            // cut
            auto next = l->next;
            l->next = nullptr;
            // append
            end->next = l;
            // forward
            l = next;
            end = end->next;
            if(r) r = r->next;
        }

        return dummy.next;
    }
};

Feb/9/2020 code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head || !head->next) return head;

        auto dummy = ListNode{INT_MIN};
        auto ptr = &dummy;

        auto l = head;
        auto r = head->next;

        // invariance r >= l
        // invariance l is the head, no node points to l

        while(l)
        {
            // the last node
            if (!r)
            {
                ptr->next = l;
                break;
            }
            if (l->val != r->val)
            {
                // remove l form the list
                l->next = nullptr;
                // splice l with the new list
                ptr->next = l;

                //increase l & r
                l = r;
                r = r->next;
                //increase ptr
                ptr = ptr->next;
                continue;
            }
            // found duplicate nodes
            if (l->val == r->val)
            {
                // continue move r unitl not duplicate
                // r may be moved to the end, r == nullptr
                while(r && l->val == r->val)
                {
                    r = r->next;
                }
                // skip this part
                l = r == nullptr ? nullptr : r;
                r = r == nullptr ? nullptr : r->next;
            }
        }

        return dummy.next;
    }
};

其他

分隔链表

LC725 分隔链表

一个链表长为N，分隔成k个连续的部分，要求相差不超过一。可以用下面的方法算出每段的长度（不知道原因）：

for(auto i = len; k > 0;)
{
    auto cut = i / k; // <----- cut 即为每段的长度。
    i -= cut;
    --k;
}

比如长为10的链表分成3分：

10 / 3 = 3, 10 - 3 = 7
7 / 2 = 3, 7 - 3 = 4
4 / 1 = 4, 4 - 4 = 0

code

auto splice_front(ListNode* head, int k)
{
    for(auto i = 1; i < k; ++i)
    {
        head = head->next;
    }

    if(head)
    {
        auto next = head->next;
        head->next = nullptr;
        return next;
    }
    else
    {
        return head;
    }
}

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* root, int k) {

        const auto len = [root]()mutable
        {
            auto cnt = 0;
            while(root)
            {
                ++cnt;
                root = root->next;
            }
            return cnt;
        }();

        const auto cut_lens = [=]()mutable
        {
            auto res = vector<int>{};
            for(auto i = len; k > 0;)
            {
                auto cut = i / k;
                res.push_back(cut);
                i -= cut;
                --k;
            }
            reverse(res.begin(), res.end());
            return res;
        }();

        auto res = vector<ListNode*>(cut_lens.size());
        transform(cut_lens.begin(), cut_lens.end(), res.begin(), 
        [&](int cut_len) mutable
        {
            auto cut_head = root;
            root = splice_front(root, cut_len);
            return cut_head;
        });

        return res;
    }
};

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        int len = lenList(head);
        vector<ListNode*> res{};
        auto cut_seq = generateCutSeq(len, k);
        auto it = cut_seq.begin();
        
        while(it != cut_seq.end())
        {
            auto cut = *it;
            auto cut_head = head;
            res.push_back(cut_head);
            head = cutList(head, cut);
            ++it;
        }

        return res;
    }

    vector<int> generateCutSeq(int len, int k)
    {
        vector<int> res{};
        while(len)
        {
            auto cut = len / k;
            if(cut == 0) cut = 1;
            res.push_back(cut);
            len -= cut;
            --k;
        }
        reverse(res.begin(), res.end());
        while(k)
        {
            res.push_back(0);
            --k;
        }
        return res;
    }

    int lenList(ListNode* head)
    {
        int len = 0;
        while(head)
        {
            head = head->next;
            ++len;
        }
        return len;
    }

    ListNode* cutList(ListNode* head, int n)
    {
        if(!head) return nullptr;
        --n;
        while(head && n)
        {
            head = head->next;
            --n;
        }

        if(!head) return nullptr;
        // cut
        auto next = head->next;
        head->next = nullptr;
        return next;
    }
};

两个一组翻转链表

LC24 两两交换链表中的节点

这个题的思路类似链表排序，每次cut下来一块链表，翻转好之后拼到dummyNode上，然后把dummyNode移动到末尾。

code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        auto dummyNode = ListNode{INT_MIN};
        auto pDummyNode = &dummyNode;
        while(head)
        {
            ListNode* next = nullptr;
            if(head->next)
            {
                next = head->next->next;
            }
            pDummyNode->next = cutAndSwap(head);
            // 一定是移动到末尾，不要思维定势
            // 只有一句pDummyNode = pDummyNode->next;是不够的
            while(pDummyNode->next)
            {
                pDummyNode = pDummyNode->next;
            }
            
            head = next;
        }
        return dummyNode.next;
    }

    ListNode* cutAndSwap(ListNode* head)
    {
        auto first  = head;
        auto second = head->next;
        if(!second) {
            first->next = nullptr;
            return first;
        }

        first->next = nullptr;
        second->next = first;

        return second;
    }
};

K个一组翻转链表

LC24 K个一组翻转链表

按照裁剪，变换，拼接的思路来做，这个题根本不配hard

裁剪：从当前指针开始，往后移动k-1位，就是要裁下来的部分。
变换：翻转链表
拼接上即可

注意的细节：

在翻转链表之后可以把尾节点和头节点一并传回，这样就不用遍历一次把新链表的尾节点移动到位了。
在变换之前一定别忘了备份next指针
在结束完拼接之后，别忘了更新新链表的尾节点和旧链表的头节点

code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto dummy = ListNode{INT_MIN};
        auto ptr = &dummy;
        if (k == 1 || !head) return head;

        while(head)
        {
            // slice
            auto back = head;
            for(int i = 1; i < k && back; ++i)
            {
                back = back->next;
            }

            if(back)
            {
                auto next = back->next;
                back->next = nullptr;
                // transform
                auto [newHead, newBack] = rotateList(head);
                //splice
                ptr->next = newHead;
                ptr = newBack;
                head = next;
                continue;
            }

            // back is nullptr, the last part of the list
            // just do splice will be OK
            ptr->next = head;
            head = nullptr;
        }

        return dummy.next;
    }

    pair<ListNode*, ListNode*> rotateList(ListNode* head)
    {
        auto back = head;
        ListNode* newHead = nullptr;
        while(head)
        {
            auto next = head->next;
            head->next = newHead;
            newHead = head;
            head = next;
        }
        return {newHead, back};
    }
};

将链表中偶数节点放在奇数节点后面

LC328 Odd Even Linked List

使用两个dummyNode，一个供奇数节点用，另一个供偶数节点用。将从原来链表取下的节点分别放到两个dummyNode后面。之后再将偶数的链表头链接在奇数的链表末尾。

code

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        auto dummy_even = ListNode{INT_MAX};
        auto dummy_odd  = ListNode{INT_MAX};
        auto p_even = &dummy_even;
        auto p_odd  = &dummy_odd;

        auto odd = true;
        while(head)
        {
            // backup
            auto next = head->next;
            // slice
            head->next = nullptr;
            // splice
            if(odd)
            {
                p_odd->next = head;
                p_odd = p_odd->next;
            }
            else
            {
                p_even->next = head;
                p_even = p_even->next;
            }
            odd = !odd;
            head = next;
        }

        p_odd->next = dummy_even.next;
        return dummy_odd.next;
    }
};

重排链表

LC143 重排链表

code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head || !head->next) return;

        int len = 0;
        auto ptr = head;
        while(ptr)
        {
            ptr = ptr->next;
            ++len;
        }

        len = (len & 1) ? len / 2 + 1 : len / 2;
        ptr = head;
        ListNode* beforePtr = nullptr;
        for(int i = 0; i < len; ++i)
        {
            beforePtr = ptr;
            ptr = ptr->next;
        }

        // slice
        beforePtr->next = nullptr;
        // transform
        auto newHead = rotateList(ptr);

        auto dummy = ListNode{INT_MIN};
        ptr = &dummy;
        // splice
        while(newHead && head)
        {
            auto headNext = head->next;
            auto newHeadNext = newHead->next;

            head->next = nullptr;
            newHead->next = nullptr;
            
            ptr->next = head;
            ptr = ptr->next;
            ptr->next = newHead;
            ptr = ptr->next;

            head = headNext;
            newHead = newHeadNext;

        }

        if(head)
        {
            ptr->next = head;
            head->next = nullptr;
        }

        if(newHead)
        {
            ptr->next = newHead;
            newHead->next = nullptr;
        }
    }

    ListNode* rotateList(ListNode* head)
    {
        ListNode* newHead = nullptr;
        while(head)
        {
            auto next = head->next;
            head->next = newHead;
            newHead = head;
            head = next;
        }
        return newHead;
    }
};

扁平化多级双向链表

LC430 扁平化多级双向链表

使用两个辅助函数insert和get_back，将有child不为空的节点的child插入到当前链表中，之后清除child指针即可。

code

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

void insert(Node* pos, Node* front, Node* back)
{
    auto next = pos->next;

    // link pos with front
    pos->next = front;
    front->prev = pos;

    // link back with next
    back->next = next;
    if(next)
    {
        next->prev = back;
    }
}

auto get_back(Node* front)
{
    while(front->next)
    {
        front = front->next;
    }
    return front;
}

class Solution {
public:
    Node* flatten(Node* head) {
        auto ohead = head;
        while(head)
        {
            if(head->child)
            {
                insert(head, head->child, get_back(head->child));
            }
            head->child = nullptr;
            head = head->next;
        }

        return ohead;
    }
};