分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
 
function partition(head: ListNode | null, x: number): ListNode | null {
    //双链表解法，一个链表记录小于 x 的，一个记录大于 x 的，然后再合并
    let dommy_small = new ListNode(0)
    const small_head = dommy_small
    let dommy_large = new ListNode(0)
    const large_head = dommy_large
 
    let curr = head
    while(curr){
        if(curr.val<x){
            dommy_small.next = curr
            dommy_small = dommy_small.next
            
        }else {
            dommy_large.next =curr
            dommy_large = dommy_large.next
        }
        curr = curr.next
    }
    dommy_small.next = large_head.next
    dommy_large.next = null
 
    return small_head.next
};