分隔链表

七崽爱吃小饼干2026/01/07阅读 0专栏算法合集

分隔链表

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

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

示例 1：

codeType

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

codeType

输入：head = [2,1], x = 2
输出：[1,2]

提示：

链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200

解法：

/**
 * 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的节点取出来按照原来的顺序组成一条新链表l1
    // 剩下的节点按照原来的顺序组成l2
    // 然后拼接l1和l2
    const Dummy = new ListNode()
    Dummy.next = head
    let p = Dummy
    let l1 = new ListNode() // 小于特定值的链表
    let l2 = new ListNode() // 大于特定值的脸部
    let p1 = l1 
    let p2 = l2
    while(p.next !== null){
        if(p.next.val < x){
            p1.next = p.next
            p1 = p1.next
        }else{
            p2.next = p.next
            p2 = p2.next
        }
        p = p.next
    }
    p1.next = l2.next // 小于特定值链表的末尾接到l2的头部
    p2.next = null
    return l1.next
};