86.分隔链表

题目:86.分隔链表

给你一个链表的头节点 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

思路

1. 初始化两个指针：

   • 使用两个指针 less 和 greater 分别指向两个新的虚拟头节点，用于分别存储小于 x 的节点和大于或等于 x 的节点。
   • 另外，使用两个指针 lessCurrent 和 greaterCurrent 作为两个子链表的尾部指针，来构建链表。

2. 遍历原链表：

   • 遍历整个链表，将每个节点根据其值分配到相应的子链表中。
   • 如果节点的值小于 x，则将其追加到 lessCurrent 链表中。
   • 如果节点的值大于或等于 x，则将其追加到 greaterCurrent 链表中。

3. 连接两个子链表：

   • 将 less 子链表与 greater 子链表连接起来。
   • 注意：greaterCurrent 的最后一个节点需要指向 null，以防止形成环。

4. 返回结果：

   • 返回新的头节点，即 less 子链表的头节点。

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

代码

public ListNode partition(ListNode head, int x) {
    // 创建两个虚拟头节点
    ListNode less = new ListNode(0);
    ListNode greater = new ListNode(0);
    // 创建两个指针lessCurrent和greaterCurrent指向当前节点
    ListNode lessCurrent = less;
    ListNode greaterCurrent = greater;
    ListNode current = head;
    // 遍历链表，将节点分配到相应子链表
    while (current != null) {
        if (current.val >= x) {
            greaterCurrent.next = current;
            greaterCurrent = greaterCurrent.next;
        } else {
            lessCurrent.next = current;
            lessCurrent = lessCurrent.next;
        }
        current = current.next;
    }
    // 连接两个子链表，并确保最后节点的 next 指向 null
    greaterCurrent.next = null;
    lessCurrent.next = greater.next;
    // 返回小于 x 子链表的头节点
    return less.next;
}