算法题题解：分隔链表
Problem: 86. 分隔链表
题目描述：
给定一个链表和一个值 x，要求将链表重新排列，所有小于 x 的节点放在前面，所有大于或等于 x 的节点放在后面。要求保留节点的相对顺序。
解题思路：
因为是链表而不是数组，构建子链不增加空间复杂度。勇敢地构造子链即可，无需考虑节点交换。
我们可以通过创建两个链表来分别存储小于 x 和大于等于 x 的节点，并最终将这两个链表连接起来。这种方法可以保证在一次遍历链表的过程中完成分割操作。
具体步骤如下：
-
虚拟头节点：使用两个虚拟头节点，一个用于保存小于
x的节点链表，另一个用于保存大于等于x的节点链表。虚拟头节点可以简化链表操作，避免处理头节点的特殊情况。 -
遍历链表：通过遍历原始链表，遇到小于
x的节点，放入小于x的链表；遇到大于或等于x的节点，放入大于等于x的链表。 -
连接链表：遍历完成后，将两个链表连接起来，并确保大于等于
x的链表末尾指向NULL，防止形成环。 -
返回新链表头：最后返回重新排列后的链表头部。
解题过程：
-
定义虚拟头节点：使用
lowDummy和highDummy作为小于x和大于等于x的链表的虚拟头节点。 -
遍历链表：我们通过遍历原始链表，将每个节点根据其值加入对应的链表（
low或high）。 -
处理边界情况：遍历结束后，确保大于等于
x的链表以NULL结尾。 -
连接两个链表：将小于
x的链表的末尾与大于等于x的链表的头部连接起来。
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* partition(struct ListNode* head, int x) {
// 定义两个虚拟头节点，分别用于存放小于x的和大于等于x的节点
struct ListNode lowDummy, highDummy;
// 初始化两个指针用于遍历链表并构建两个链表
struct ListNode *low = &lowDummy, *high = &highDummy;
struct ListNode *p = head;
// 初始化虚拟头节点的next指针为空，防止产生垃圾数据
lowDummy.next = NULL;
highDummy.next = NULL;
// 遍历原链表并进行分割
while (p) {
if (p->val < x) {
low->next = p; // 将当前节点加入到小于x的链表中
low = low->next;
} else {
high->next = p; // 将当前节点加入到大于等于x的链表中
high = high->next;
}
p = p->next; // 移动到下一个节点
}
// 终止大于等于x的链表，防止形成环
high->next = NULL;
// 将小于x的链表与大于等于x的链表连接起来
low->next = highDummy.next;
// 返回小于x的链表头部
return lowDummy.next;
}
复杂度分析：
-
时间复杂度：O(n)
- 我们只遍历一次链表，进行一次分割和连接操作，因此时间复杂度为 O(n)，其中
n是链表中的节点个数。
- 我们只遍历一次链表，进行一次分割和连接操作，因此时间复杂度为 O(n)，其中
-
空间复杂度：O(1)
- 只用了几个指针来保存链表的分割和连接状态，并没有使用额外的空间来存储数据，因此空间复杂度为 O(1)。
总结：
通过使用两个虚拟头节点，我们可以很方便地将链表中的节点分割成两部分（小于 x 和大于等于 x），并在最后将它们连接起来。这样不仅简化了代码结构，而且避免了复杂的头节点处理，使得代码更为简洁明了。
这种方法在时间和空间上都具有较好的性能，适合处理大规模链表的分隔问题。
这篇文章详细描述了解题思路、代码实现和复杂度分析，供大家参考学习。
谢谢观看！
原文地址：https://blog.csdn.net/m0_74412436/article/details/142645585
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！