面试题 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)
关键点总结
- 头插法与尾插法的结合：小于x的节点用头插法，大于等于x的节点用尾插法
- 边界处理：注意处理空链表和单节点链表的情况
- 指针操作：在修改指针前保存下一个节点，避免链表断裂
- 尾节点处理：确保尾节点的next为NULL，避免形成环
应用场景
这种链表分割技巧在以下场景中有应用：
- 快速排序的链表版本：分割操作是快速排序的核心
- 数据过滤：根据条件将数据分成两部分
- 负载均衡：将任务根据优先级分配到不同队列
总结
这道题考察了链表的基本操作和双指针技巧：
- 核心思路：通过头插法和尾插法的组合实现链表分割
- 灵活性：题目不要求保持相对顺序，给了我们更多的操作空间
- 指针操作：熟练掌握链表的插入、删除操作是关键
- 边界情况：注意处理空链表、单节点链表等特殊情况
掌握这种链表分割技巧对于理解更复杂的链表算法（如链表排序）很有帮助。
