面试题 02.04 分割链表题解与详细分析

题目描述

给你一个链表的头节点 head 和一个特定值 x，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你不需要保留每个分区中各节点的初始相对位置。

示例

示例 1：

输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2 输出：[1,2]

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

解题思路

这道题要求将链表分割成两部分：所有小于 x 的节点在前，大于或等于 x 的节点在后。关键点在于不需要保持每个分区内节点的原始相对顺序。

核心思想

使用双指针方法：

• 对于小于 x 的节点，采用头插法插入到新链表头部
• 对于大于等于 x 的节点，采用尾插法插入到新链表尾部
• 这样就能保证所有小于 x 的节点都在大于等于 x 的节点之前

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    struct ListNode* newtail = NULL;
    struct ListNode* temp = NULL;
    while(cur) {
        temp = cur->next; // 保存下一个节点
        if(cur->val < x) { // 小于x的节点：头插法
            if(newhead == NULL) {
                newhead = newtail = cur;
                newhead->next = NULL;
            } else {
                cur->next = newhead;
                newhead = cur;
            }
        } else { // 大于等于x的节点：尾插法
            if(newhead == NULL) {
                newhead = newtail = cur;
                newhead->next = NULL;
            } else {
                newtail->next = cur;
                newtail = cur;
                newtail->next = NULL;
            }
        }
        cur = temp; // 移动到下一个节点
    }
    return newhead;
}

代码详解

变量说明

• cur：当前遍历的节点
• newhead：新链表的头节点
• newtail：新链表的尾节点
• temp：临时保存下一个节点

核心逻辑

while(cur) {
    temp = cur->next; // 保存下一个节点
    if(cur->val < x) { // 头插法：将节点插入到链表头部
        if(newhead == NULL) {
            newhead = newtail = cur;
            newhead->next = NULL;
        } else {
            cur->next = newhead;
            newhead = cur;
        }
    } else { // 尾插法：将节点插入到链表尾部
        if(newhead == NULL) {
            newhead = newtail = cur;
            newhead->next = NULL;
        } else {
            newtail->next = cur;
            newtail = cur;
            newtail->next = NULL;
        }
    }
    cur = temp; // 移动到下一个节点
}

执行过程可视化

以示例 1 head = [1,4,3,2,5,2], x = 3 为例：

初始状态： 链表：1->4->3->2->5->2->NULL newhead = NULL, newtail = NULL

第 1 步：节点 1 (值 1 < 3) 头插法：newhead -> 1 -> NULL, newtail -> 1

第 2 步：节点 4 (值 4 >= 3) 尾插法：newhead -> 1 -> 4 -> NULL, newtail -> 4

第 3 步：节点 3 (值 3 >= 3) 尾插法：newhead -> 1 -> 4 -> 3 -> NULL, newtail -> 3

第 4 步：节点 2 (值 2 < 3) 头插法：newhead -> 2 -> 1 -> 4 -> 3 -> NULL, newtail -> 3

第 5 步：节点 5 (值 5 >= 3) 尾插法：newhead -> 2 -> 1 -> 4 -> 3 -> 5 -> NULL, newtail -> 5

第 6 步：节点 2 (值 2 < 3) 头插法：newhead -> 2 -> 2 -> 1 -> 4 -> 3 -> 5 -> NULL, newtail -> 5

最终结果：2->2->1->4->3->5->NULL

优化与改进

方法二：双链表法（保持相对顺序）

如果我们希望保持每个分区内节点的相对顺序，可以使用两个链表：

struct ListNode* partition(struct ListNode* head, int x) {
    // 创建两个哑节点
    struct ListNode less_dummy, ge_dummy;
    struct ListNode* less_tail = &less_dummy;
    struct ListNode* ge_tail = &ge_dummy;
    less_dummy.next = NULL;
    ge_dummy.next = NULL;
    struct ListNode* cur = head;
    while (cur != NULL) {
        if (cur->val < x) { // 添加到小于x的链表
            less_tail->next = cur;
            less_tail = cur;
        } else { // 添加到大于等于x的链表
            ge_tail->next = cur;
            ge_tail = cur;
        }
        cur = cur->next;
    }
    // 连接两个链表
    less_tail->next = ge_dummy.next;
    ge_tail->next = NULL;
    return less_dummy.next;
}

输出结果： [1,2,2,4,3,5]（保持相对顺序）

方法三：原地分割

struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    struct ListNode* insert_pos = NULL;
    while (cur != NULL) {
        if (cur->val < x) {
            if (insert_pos != NULL) { // 将当前节点移动到insert_pos之后
                if (prev != NULL) {
                    prev->next = cur->next;
                }
                struct ListNode* temp = insert_pos->next;
                insert_pos->next = cur;
                cur->next = temp;
                insert_pos = cur;
                cur = prev->next;
            } else {
                insert_pos = cur;
                prev = cur;
                cur = cur->next;
            }
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

复杂度分析

原方法

• 时间复杂度：O(n)，只需遍历链表一次
• 空间复杂度：O(1)，只使用常数级别的额外空间

双链表法

• 时间复杂度：O(n)
• 空间复杂度：O(1)

关键点总结

1. 头插法与尾插法的结合：小于 x 的节点用头插法，大于等于 x 的节点用尾插法
2. 边界处理：注意处理空链表和单节点链表的情况
3. 指针操作：在修改指针前保存下一个节点，避免链表断裂
4. 尾节点处理：确保尾节点的 next 为 NULL，避免形成环

应用场景

这种链表分割技巧在以下场景中有应用：

1. 快速排序的链表版本：分割操作是快速排序的核心
2. 数据过滤：根据条件将数据分成两部分
3. 负载均衡：将任务根据优先级分配到不同队列

总结

这道题考察了链表的基本操作和双指针技巧：

1. 核心思路：通过头插法和尾插法的组合实现链表分割
2. 灵活性：题目不要求保持相对顺序，给了我们更多的操作空间
3. 指针操作：熟练掌握链表的插入、删除操作是关键
4. 边界情况：注意处理空链表、单节点链表等特殊情况

掌握这种链表分割技巧对于理解更复杂的链表算法（如链表排序）很有帮助。