algo-aha

要在节点前插入，可以使用dummy节点，或者使用指向指针的指针；如果两种都不用，只能特殊处理头节点前的插入。

可以使用指向指针的指针，是因为虽然遍历时修改了指针的值，但指针的地址不变，前一个节点仍能指向修改后的指针。

记住要更新头指针，修改链表的函数或者返回新的头指针，或者更新头指针的指针。

使用`while (node->next)`循环的情况：
// 停在尾节点
while (node->next) {
    node = node->next;
}

// 删除节点
while (node->next) {
    // 循环里node->next是当前节点，node是前一节点
    ...
}

链表排序

• https://leetcode.com/problems/insertion-sort-list/

// 插入排序
ListNode* insertionSortList(ListNode* head) {
    ListNode dummy(-1);
    while (head) {
        auto next = head->next;
        
        auto prev = &dummy;
        while (prev->next && head->val >= prev->next->val) {
            prev = prev->next;
        }
        // 循环结束时找到插入位置
        head->next = prev->next;
        prev->next = head;
        
        head = next;
    }
    return dummy.next;
}

反转链表

• https://leetcode.com/problems/reverse-linked-list/

把节点一个个取出，插入另一个链表头。观察循环中的赋值顺序，刚好就是个轮转：head->next => list => head => next。

ListNode* reverseList(ListNode* head) {
    ListNode *list = NULL;
    while (head) {
        auto next = head->next;
        head->next = list;
        list = head;
        head = next;
    }
    return list;
}

删除倒数第n个节点

• https://leetcode.com/problems/remove-nth-node-from-end-of-list/

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(-1); // 可能删除头节点
    dummy.next = head;

    auto fast = &dummy;
    // 找倒数第n节点前一节点：
    // fast先走n步、后面while(fast->next)是唯一正确写法，可以配合!fast检测n值合法
    // <del>fast先走n+1步、后面while(fast)的写法，若配合!fast检测n值会出错</del>
    for (int i = 0; i < n && fast; i++) fast = fast->next;
    if (!fast) return head;

    auto slow = &dummy;
    while (fast->next) { // fast最后停在尾节点
        fast = fast->next;
        slow = slow->next;
    }
    // slow是待删除节点的前一节点
    auto next = slow->next->next;
    delete slow->next;
    slow->next = next;

    return dummy.next;
}

快慢指针

• https://leetcode.com/problems/middle-of-the-linked-list/
• https://leetcode.com/problems/palindrome-linked-list/
• https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

前进条件while (fast && fast->next) { ... }，不管fast初始走没走一步，slow在链表长奇数时总指向正中间节点。

若fast初始先走一步（记这种写法），slow在链表长偶数时指向前半段尾节点（由两节点情况推得）。由单节点情况可知，fast==NULL可判断链表奇数长。

if (!head) return;
auto fast = head->next, slow = head;
while (fast && fast->next) {
    fast = fast->next->next;
    slow = slow->next;
}

若fast初始没有先走，slow在链表长偶数时指向后半段头节点（由两节点情况推得）。由单节点情况可知，fast!=NULL可判断链表奇数长。比fast初始先走写法麻烦在：如需前半段尾节点，比如需要切断链表，得用个prev保存最近slow。

if (!head) return;
auto fast = head, slow = head;
while (fast && fast->next) {
    fast = fast->next->next;
    slow = slow->next;
}

链表环的入口点

• https://leetcode.com/problems/linked-list-cycle-ii/

先快慢指针，若fast、slow相遇则有环；相遇后让一指针回到链表头，再同速跑，再相遇处就是入口点。

这是因为，假设链表头到入口点要a步，入口点到相遇点要b步，slow进环后不到一圈就被fast追上，从开始到相遇slow走了a+b步，fast走了a+b+k*LoopSize=2*(a+b)步，a=k*LoopSize-b。一指针回到链表头再同速跑，再跑a=k*LoopSize-b步，环中相当于倒退b步，再相遇处就是入口点。

ListNode *detectCycle(ListNode *head) {
    auto fast = head, slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) { // 相遇，再同速跑
            fast = head;
            while (fast != slow) {
                fast = fast->next;
                slow = slow->next;
            }
            return fast;
        }
    }
    return NULL;
}

扩展：快慢指针应用在数组

两链表的交点

• https://leetcode.com/problems/intersection-of-two-linked-lists/

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    // pa跑完链表A跑链表B，pb跑完链表B跑链表A，
    // 最终跑到同一交点（有交点到交点，无交点到NULL节点）
    auto pa = headA, pb = headB;
    while (pa != pb) {
        pa = pa ? pa->next : headB;
        pb = pb ? pb->next : headA;
    }
    return pa;
}

链表右旋k步

• https://leetcode.com/problems/rotate-list/

不用"一指针先走k步、再两指针同步走"的办法，同样的指针移动操作数，逻辑更复杂。

ListNode* rotateRight(ListNode* head, int k) {
    if (!head) return NULL;
    // 先变循环链表
    auto tail = head;
    int len = 1;
    while (tail->next) {
        tail = tail->next;
        len++;
    }
    tail->next = head;
    // 再断开
    k %= len;
    for (int i = 0; i < len - k; i++)
        tail = tail->next;
    auto newHead = tail->next;
    tail->next = NULL;
    return newHead;
}

在循环有序链表中插入

• https://leetcode.com/problems/insert-into-a-cyclic-sorted-list/

ListNode* insert(ListNode* node, int x) {
    if (!node) {
        auto nn = new ListNode(x);
        nn->next = nn;
        return nn;
    }

    // 能否在某位置后插入：
    // 以node为头的话，循环中只判断非尾的之前位置；
    // 这些位置都不行时，通过画图例可知，尾位置总是可行。
    auto p = node;
    while (p->next != node) {
        if (p->val <= x && x <= p->next->val) break;
        if (p->val > p->next->val && (x >= p->val || x <= p->next->val)) break;
        p = p->next;    
    }
    // 这时在p后插入
    auto nn = new ListNode(x);
    nn->next = p->next;
    p->next = nn;
    return nn;
}

链表按层展平

链表展平：遍历第一层，每遇到子链表就把它接到尾指针的后面，这样随着尾指针后移就按层展平了。

取消展平：链表展平并没有丢失父子关系，只是增加了前后关系，只要取消这些前后关系。可以反向遍历，把子节点指针所指的与它前面一个分离。