链表核心算法实战：从基础操作到复杂变换

3. 重排链表

这道题的核心在于将链表拆分为两部分，反转后半部分，然后交替合并。

1. 找中间节点，分成两个链表。
2. 将第二条链表逆序。
3. 合并两条链表。

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next || !head->next->next) return;
        ListNode* slow = head, *fast = head;
        // 找到中间结点，将链表断开
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        ListNode* head2 = new ListNode(0);
        ListNode* cur = slow->next;
        slow->next = nullptr;
        
        // 反转第二条链表，头插
        while (cur) {
            ListNode* next = cur->next;
            cur->next = head2->next;
            head2->next = cur;
            cur = next;
        }
        
        // 合并两条链表
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        ListNode* cur1 = head, *cur2 = head2->next;
        while (cur1) {
            prev->next = cur1;
            prev = prev->next;
            cur1 = cur1->next;
            if (cur2) {
                prev->next = cur2;
                cur2 = cur2->next;
                prev = prev->next;
            }
        }
        delete head2;
        delete ret;
    }
};

4. 合并 K 个升序链表

合并两个有序列表比较简单，用双指针依次比较即可。合并 k 个时，可以用堆快速找到最小元素，或者采用分治递归的方式减少比较次数。

思路一（堆）： 将所有头节点放入小根堆，每次取出最小值加入结果链表。

思路二（递归/分治）： 两两合并，让长度相近的链表先合并，降低总计算量。

// 利用优先级队列的思想，建堆
struct cmp {
    bool operator()(ListNode* l1, ListNode* l2) {
        return l1->val > l2->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
        for (auto l : lists) {
            if (l) heap.push(l);
        }
        
        ListNode* head = new ListNode(0);
        ListNode* prev = head;
        while (!heap.empty()) {
            ListNode* t = heap.top();
            heap.pop();
            prev->next = t;
            prev = prev->next;
            if (t->next) {
                t = t->next;
                heap.push(t);
            }
        }
        prev = head->next;
        delete head;
        return prev;
    }
};

// 法三：分治——递归，时间复杂度 O(n*k*logk)
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
    
    ListNode* merge(vector<ListNode*>& lists, int left, int right) {
        if (left > right) return nullptr;
        if (left == right) return lists[left];
        
        int mid = (left + right) >> 1;
        ListNode* l1 = merge(lists, left, mid);
        ListNode* l2 = merge(lists, mid + 1, right);
        return mergeTosort(l1, l2);
    }
    
    ListNode* mergeTosort(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        
        ListNode cur;
        ListNode* prev = &cur;
        cur.next = nullptr;
        
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                prev = prev->next = l1;
                l1 = l1->next;
            } else {
                prev = prev->next = l2;
                l2 = l2->next;
            }
        }
        if (l1) prev->next = l1;
        if (l2) prev->next = l2;
        return cur.next;
    }
};

5. K 个一组翻转链表

我们可以把链表按 k 个为一组进行分组，组内进行反转，并记录反转后的头尾节点，使其可以和前、后连接起来。

可以先求出一共需要逆序多少组，然后重复 n 次长度为 k 的链表的逆序即可。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int n = 0;
        ListNode* cur = head;
        while (cur) {
            n++;
            cur = cur->next;
        }
        
        n /= k;
        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        cur = head;
        
        while (n--) {
            ListNode* tmp = cur;
            for (int i = 0; i < k; i++) {
                ListNode* next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
                cur = next;
            }
            prev = tmp;
        }
        prev->next = cur;
        prev = newhead->next;
        delete newhead;
        return prev;
    }
};