链表核心算法实战解析

3. 重排链表

思路： 将链表分为两半，后半部分反转，然后交替合并。这是典型的'分治 + 双指针'组合拳。

1. 找中点：快慢指针，fast 走两步，slow 走一步。
2. 断链与反转：断开 slow 指向，将后半段头插法反转。
3. 合并：交替连接两个子链表。

class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head || !head->next || !head->next->next) return;
        
        // 1. 找到中间节点
        ListNode* slow = head, *fast = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 2. 断开并反转第二条链表
        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;
        }
        
        // 3. 合并两条链表
        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 = t;
            
            if(t->next) {
                heap.push(t->next);
            }
        }
        
        ListNode* result = head->next;
        delete head;
        return result;
    }
};

// 方法二：分治递归
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 head;
        ListNode* prev = &head;
        
        while(l1 && l2){
            if(l1->val <= l2->val){
                prev->next = l1;
                l1 = l1->next;
            } else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }
        
        prev->next = l1 ? l1 : l2;
        return head.next;
    }
};

5. K 个一组翻转链表

思路： 按 K 个节点为一组进行切割，组内反转，组间连接。需要先统计总长度以确定需要翻转多少组。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int n = 0;
        ListNode* cur = head;
        while(cur){
            n++;
            cur = cur->next;
        }
        
        int groups = n / k;
        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        cur = head;
        
        while(groups--){
            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;
        ListNode* result = newhead->next;
        delete newhead;
        return result;
    }
};

以上五种题型涵盖了链表操作中常见的指针变换、结构重组及优化策略。实际编码时，建议多画图辅助理解指针指向变化，避免空指针异常。