11、链表的合并与拆分：合并两个有序链表、拆分链表为奇偶两部分

链表操作里，合并和拆分是两种非常经典的操作。我个人觉得，这两个操作特别能检验你对指针操作的理解深度。说白了，就是看你能不能把链表节点像搭积木一样，拆开再拼回去。

我在项目中遇到过好几次这样的场景：系统里有两个传感器数据流，各自按时间戳排好了序，需要合并成一个完整的数据流。还有一次是做数据分包，需要把一个链表按奇偶位置拆成两个独立的链表。嗯，今天我们就来聊聊这两个操作。

11.1 合并两个有序链表

合并两个有序链表，目标很明确：把两个已经排好序的链表，合并成一个新的有序链表。你想想看，这就像把两副按大小排好的扑克牌，合并成一整副。

常见的做法有两种：一种是新建一个链表，把节点一个个插进去；另一种是原地合并，不申请新节点。我个人更推荐第二种，因为嵌入式环境里内存很宝贵。

11.1.1 原地合并的思路

核心思路其实很简单：用两个指针分别遍历两个链表，每次比较当前节点的值，把较小的那个节点摘下来，接到新链表的尾部。

这里有个小技巧：我习惯用一个虚拟头节点（dummy head）来简化操作。这样就不用单独处理第一个节点为空的情况了。

// 合并两个有序链表，返回合并后的头指针
Node* mergeSortedLists(Node* head1, Node* head2) {
    Node dummy;          // 虚拟头节点，不存储有效数据
    Node* tail = &dummy; // tail始终指向新链表的最后一个节点
    dummy.next = NULL;

    while (head1 != NULL && head2 != NULL) {
        if (head1->data <= head2->data) {
            tail->next = head1;  // 把head1节点接过来
            head1 = head1->next; // head1指针后移
        } else {
            tail->next = head2;
            head2 = head2->next;
        }
        tail = tail->next; // tail始终指向最后一个节点
    }

    // 把剩下的节点直接接上
    if (head1 != NULL) {
        tail->next = head1;
    } else {
        tail->next = head2;
    }

    return dummy.next; // 虚拟头节点的下一个节点就是真正的头
}

11.1.2 递归写法

其实合并有序链表也可以用递归写，代码会更简洁。不过我个人不太推荐在嵌入式里用递归，因为递归深度不可控，容易爆栈。

// 递归版本，仅供参考
Node* mergeRecursive(Node* head1, Node* head2) {
    if (head1 == NULL) return head2;
    if (head2 == NULL) return head1;

    if (head1->data <= head2->data) {
        head1->next = mergeRecursive(head1->next, head2);
        return head1;
    } else {
        head2->next = mergeRecursive(head1, head2->next);
        return head2;
    }
}

11.2 拆分链表为奇偶两部分

拆分链表，就是把一个链表按某种规则分成两个。最常见的规则是按位置：奇数位置的节点组成一个链表，偶数位置的节点组成另一个链表。

你想想看，这就像排队报数，喊1的站左边，喊2的站右边。

11.2.1 奇偶拆分的实现

实现思路也很直接：用两个指针分别遍历奇数位置和偶数位置。每次把奇数位置的节点摘下来，接到奇数链表尾部；再把偶数位置的节点摘下来，接到偶数链表尾部。

// 拆分链表为奇偶两部分
// oddHead: 奇数位置链表的头指针
// evenHead: 偶数位置链表的头指针
void splitOddEven(Node* head, Node** oddHead, Node** evenHead) {
    if (head == NULL) {
        *oddHead = NULL;
        *evenHead = NULL;
        return;
    }

    Node oddDummy;   // 奇数链表的虚拟头节点
    Node evenDummy;  // 偶数链表的虚拟头节点
    Node* oddTail = &oddDummy;
    Node* evenTail = &evenDummy;
    oddDummy.next = NULL;
    evenDummy.next = NULL;

    int position = 1; // 位置从1开始计数
    Node* current = head;
    Node* nextNode;

    while (current != NULL) {
        nextNode = current->next; // 先保存下一个节点
        current->next = NULL;     // 断开当前节点

        if (position % 2 == 1) {
            // 奇数位置，接到奇数链表
            oddTail->next = current;
            oddTail = current;
        } else {
            // 偶数位置，接到偶数链表
            evenTail->next = current;
            evenTail = current;
        }

        current = nextNode;
        position++;
    }

    *oddHead = oddDummy.next;
    *evenHead = evenDummy.next;
}

11.2.2 另一种拆分方式：按值拆分

有时候我们不是按位置拆分，而是按节点值的大小来拆分。比如把小于某个阈值的节点放到一个链表，大于等于的放到另一个链表。这种操作在数据过滤时很常见。

// 按值拆分：小于threshold的放left，大于等于的放right
void splitByValue(Node* head, int threshold, Node** leftHead, Node** rightHead) {
    Node leftDummy, rightDummy;
    Node* leftTail = &leftDummy;
    Node* rightTail = &rightDummy;
    leftDummy.next = NULL;
    rightDummy.next = NULL;

    Node* current = head;
    Node* nextNode;

    while (current != NULL) {
        nextNode = current->next;
        current->next = NULL;

        if (current->data < threshold) {
            leftTail->next = current;
            leftTail = current;
        } else {
            rightTail->next = current;
            rightTail = current;
        }

        current = nextNode;
    }

    *leftHead = leftDummy.next;
    *rightHead = rightDummy.next;
}

11.3 核心逻辑流程图

下面这张图展示了合并和拆分的核心流程，我建议你仔细看看，理解指针是怎么移动的。

11.4 常见问题与避坑指南

操作链表时，有几个地方特别容易出问题。我把自己踩过的坑总结一下，你写代码时多留个心眼。

问题	原因	解决方法
合并后链表成环	最后一个节点的next没有置NULL	每次摘节点时，先把current->next置NULL
拆分后丢失节点	遍历时没有保存下一个节点的指针	先保存nextNode，再操作当前节点
虚拟头节点忘记释放	dummy节点在栈上，但有人习惯用malloc	尽量用栈上的虚拟节点，省去释放的麻烦
递归合并导致栈溢出	链表太长，递归深度过大	用迭代代替递归

11.5 总结

合并和拆分，说白了就是指针的重新排列。你只要记住三点：

• 用虚拟头节点：简化边界处理，代码更干净
• 先保存后操作：修改指针前，先保存下一个节点的地址
• 断开要彻底：摘下来的节点，next一定要置NULL

掌握了这两个操作，你对链表的理解会上一个台阶。后面遇到更复杂的链表操作，比如链表排序、链表反转等，你会发现思路都是相通的。