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

链表核心算法实战

链表操作是数据结构面试中的高频考点，涉及指针变换、内存管理及递归思维。以下整理五道经典题目，涵盖模拟、堆结构、分治等策略，代码均基于 C++ 实现。

1. 两数相加

两个链表逆序存储数字，个位对齐。直接遍历相加即可，关键在于处理进位。若最高位仍有进位，需新增节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* cur1 = l1, *cur2 = l2;
        ListNode* dummyHead = new ListNode(0);
        ListNode* tail = dummyHead;
        int carry = 0;

        while (cur1 || cur2 || carry) {
            if (cur1) {
                carry += cur1->val;
                cur1 = cur1->next;
            }
            if (cur2) {
                carry += cur2->val;
                cur2 = cur2->next;
            }
            ListNode* node = new ListNode(carry % 10);
            tail->next = node;
            tail = tail->next;
            carry /= 10;
        }

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

2. 两两交换链表中的节点

通过调整指针指向完成节点交换。使用虚拟头结点简化边界处理，注意保存 next 指针防止断链。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;
        
        ListNode* dummyHead = new ListNode(0, head);
        ListNode* prev = dummyHead;
        ListNode* cur = head;

        while (cur && cur->next) {
            ListNode* nextNode = cur->next;
            ListNode* nNext = nextNode->next;

            // 交换
            prev->next = nextNode;
            cur->next = nNext;
            nextNode->next = cur;

            // 移动指针
            prev = cur;
            cur = nNext;
        }

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

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;
    }
};