链表经典算法题解：相加、重排与合并

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* p1 = head, *p2 = head2->next;

        while (p1) {
            prev->next = p1;
            prev = prev->next;
            p1 = p1->next;
            if (p2) {
                prev->next = p2;
                p2 = p2->next;
                prev = prev->next;
            }
        }

        delete head2;
        delete ret;
    }
};

4. 合并 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* dummyHead = new ListNode(0);
        ListNode* prev = dummyHead;

        while (!heap.empty()) {
            ListNode* t = heap.top();
            heap.pop();
            prev->next = t;
            prev = prev->next;

            if (t->next) {
                heap.push(t->next);
            }
        }

        ListNode* result = dummyHead->next;
        delete dummyHead;
        return result;
    }
};

方法二：分治递归

利用二分思想，将链表列表两两合并，减少比较次数。时间复杂度 O(N log K)。

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        return merge(lists, 0, lists.size() - 1);
    }

private:
    ListNode* merge(vector<ListNode*>& lists, int left, int right) {
        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 mergeTwoSortedLists(l1, l2);
    }

    ListNode* mergeTwoSortedLists(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 个节点为一组进行分组，组内反转后连接。需先计算总长度确定完整组数，剩余不足 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* dummyHead = new ListNode(0);
        ListNode* prev = dummyHead;
        cur = head;

        while (groups--) {
            ListNode* groupStart = cur;
            for (int i = 0; i < k; ++i) {
                ListNode* next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
                cur = next;
            }
            prev = groupStart;
        }

        prev->next = cur;
        ListNode* result = dummyHead->next;
        delete dummyHead;
        return result;
    }
};