LC

链表重排
链表排序

导语

链表题大多属于思路很直接，但是代码实现复杂+细节多。本文收集2道细节拉满的链表题，方便日后复习时细品。

链表重排

这个题十分直观，就是把链表后半部分掰出来，翻转，然后交错地和前半段交叉。

  • 细节一 ： 找中点
    这里的细节在于要考虑链表有可能是奇数个结点或偶数个，直接$\lfloor \frac{n}{2} \rfloor$是不对的，要换成$\lceil \frac{n}{2} \rceil$。并且，从head结点跳到中点处只需要走$\lceil \frac{n}{2} \rceil - 1$步，是比长度少1的。（Tip: 上取整的公式为$\lfloor \frac{a}{b} \rfloor = \lceil \frac{a + b - 1}{b} \rceil$)
  • 细节二 ： 翻转链表
    这里的细节主要在翻转完之后，尾结点的next指针要置空。但翻转后的尾结点是翻转前的头结点，所以事先要保存一下。
  • 细节三 ： 交错合成
    这一步的细节是循环结束的条件，此时我们用2个指针分别指向左右两段的开头。当链表有奇数个结点时，循环结束的条件为2个指针相遇；当链表有偶数个结点时，循环结束的条件为第1个指针为空。

    代码

class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head) return;

        // 求链表长度
        int n = 0;
        for(auto p = head; p; p = p->next) n++;

        // 找中点
        auto mid = head;
        for(int i = 0; i + 1 < (n + 1) / 2; i++) mid = mid->next;
        auto pre = mid, back = mid->next;

        // 翻转后半段
        while(back) {
            auto t = back->next;
            back->next = pre;
            pre = back, back = t;
        }
        mid->next = nullptr;

        // 交错合成
        while(head && head != pre) {
            auto t = pre->next;
            pre->next = head->next;
            head->next = pre;
            head = head->next->next;
            pre = t;
        }
    }
};

链表排序

这个题要求时间$O(nlogn)$, 空间$O(1)$。只能用自底向上的归并排序来写。同样是细节拉满，需要对链表足够熟练才能做到bug free写出。

细节参考代码注释。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        int n = 0;
        for(auto p = head; p; p = p->next) n++;

        for(int i = 1; i < n; i <<= 1) {  // 细节一： n不能取到，因为最后一次合并是将规模为n/2的2个有序链表合成1个
            auto cur = dummy;
            for(int j = 1; j + i <= n; j = j + i * 2) {  // 细节二： n可以取到。这里的j表示每次合成的2段中第1段的开始位置，j+i表示第2段的开始位置，j+i == n时，第2段只有1个数。
                auto p = cur->next, q = p;
                for(int k = 0; k < i; k++) q = q->next;
                int l = 0, r = 0;
                while(l < i && r < i && p && q) { // 细节三： 既需要判2段的结点数，又需要判2段是否已经走完，因为2段不一定是等长的，当链表结点数不是2的幂时，尾部会少一些数。
                    if(p->val <= q->val) cur = cur->next = p, l++, p = p->next;
                    else cur = cur->next = q, r++, q = q->next;
                }
                while(l < i && p) cur = cur->next = p, l++, p = p->next;
                while(r < i && q) cur = cur->next = q, r++, q = q->next;
                cur->next = q;  // 细节四： 每合成完2段后，需要将合成好的链表和下一次准备要合成的链表串起来
            }
        }
        return dummy->next;
    }
};