19_链表_86. 分隔链表.md

-- 链表 - mid 点击直达力扣

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

// 创建两个指针，small用于存储小于x的节点，large用于按顺序存储剩余节点
// 最后将small节点的next指向large的头部
// 注意最后需要切断large的next，防止large后续接连着其他节点
function partition(head: ListNode | null, x: number): ListNode | null {
    let small = new ListNode(0)
    let large = new ListNode(0)
    let smallHead = small
    let largeHead = large

    while (head) {
        if (head.val < x) {
            small.next = head
            small = small.next
        } else {
            large.next = head
            large = large.next
        }
        head = head.next
    }

    large.next = null
    small.next = largeHead.next
    return smallHead.next
};