算法题题解：分隔链表

Problem: 86. 分隔链表

题目描述：

给定一个链表和一个值 x，要求将链表重新排列，所有小于 x 的节点放在前面，所有大于或等于 x 的节点放在后面。要求保留节点的相对顺序。

---

解题思路：

因为是链表而不是数组，构建子链不增加空间复杂度。勇敢地构造子链即可，无需考虑节点交换。

我们可以通过创建两个链表来分别存储小于 x 和大于等于 x 的节点，并最终将这两个链表连接起来。这种方法可以保证在一次遍历链表的过程中完成分割操作。

具体步骤如下：

1. 虚拟头节点：使用两个虚拟头节点，一个用于保存小于 x 的节点链表，另一个用于保存大于等于 x 的节点链表。虚拟头节点可以简化链表操作，避免处理头节点的特殊情况。

2. 遍历链表：通过遍历原始链表，遇到小于 x 的节点，放入小于 x 的链表；遇到大于或等于 x 的节点，放入大于等于 x 的链表。

3. 连接链表：遍历完成后，将两个链表连接起来，并确保大于等于 x 的链表末尾指向 NULL，防止形成环。

4. 返回新链表头：最后返回重新排列后的链表头部。

---

解题过程：

1. 定义虚拟头节点：使用 lowDummy 和 highDummy 作为小于 x 和大于等于 x 的链表的虚拟头节点。

2. 遍历链表：我们通过遍历原始链表，将每个节点根据其值加入对应的链表（low 或 high）。

3. 处理边界情况：遍历结束后，确保大于等于 x 的链表以 NULL 结尾。

4. 连接两个链表：将小于 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;
}

---

复杂度分析：

1. 时间复杂度：O(n)

   • 我们只遍历一次链表，进行一次分割和连接操作，因此时间复杂度为 O(n)，其中 n 是链表中的节点个数。

2. 空间复杂度：O(1)

   • 只用了几个指针来保存链表的分割和连接状态，并没有使用额外的空间来存储数据，因此空间复杂度为 O(1)。

---

总结：

通过使用两个虚拟头节点，我们可以很方便地将链表中的节点分割成两部分（小于 x 和大于等于 x），并在最后将它们连接起来。这样不仅简化了代码结构，而且避免了复杂的头节点处理，使得代码更为简洁明了。

这种方法在时间和空间上都具有较好的性能，适合处理大规模链表的分隔问题。

---

这篇文章详细描述了解题思路、代码实现和复杂度分析，供大家参考学习。
谢谢观看！

原文地址：https://blog.csdn.net/m0_74412436/article/details/142645585

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！