算法题题解：分隔链表
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），并在最后将它们连接起来。这样不仅简化了代码结构，而且避免了复杂的头节点处理，使得代码更为简洁明了。
这种方法在时间和空间上都具有较好的性能，适合处理大规模链表的分隔问题。
这篇文章详细描述了解题思路、代码实现和复杂度分析，供大家参考学习。
谢谢观看！