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

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 个时，有两种主流方案：

1. 优先队列（堆）： 将所有头节点放入小根堆，每次取出最小值加入结果链表，若该节点有后继则推入堆中。时间复杂度 O(N log K)。
2. 分治递归： 类似归并排序，将 K 个链表两两分组合并，直到只剩一个。相比逐一合并，这种平衡树式的合并方式能减少比较次数。

方法一：堆优化

class Solution {
public:
    struct cmp{
        bool operator()(ListNode* l1, ListNode* l2){
            return l1->val > l2->val;
        }
    };
    
    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;
    }
};

方法二：分治递归

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;
        
        ListNode* c1 = l1, *c2 = l2;
        while(c1 && c2){
            if(c1->val <= c2->val){
                prev->next = c1;
                c1 = c1->next;
            } else{
                prev->next = c2;
                c2 = c2->next;
            }
            prev = prev->next;
        }
        if(c1) prev->next = c1;
        if(c2) prev->next = c2;
        return cur.next;
    }
};

5. K 个一组翻转链表

思路分析： 按 k 个为一组进行分组，组内反转，并记录反转后的头尾节点以便连接前后段。可以先统计总长度确定需要翻转多少组，然后重复执行长度为 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;
    }
};