面试题 02.04. 分割链表

/**
 * 给你一个链表的头节点 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 {
	let newNode = new ListNode(0, head);
	let current = head; // 遍历用
	let p = newNode; // 存储小于x的尾节点
	while (current) {
		if (current.val < x) {
			// 当前值小于x时
			p = current;
		} else {
			// 当前值大于或等于x时，从当前位置找第一个小于x的节点
			let cur = current.next;
			let first = null;
			while (cur && cur.val >= x) {
				if (first == null) {
					first = cur;
				}
			}
		}
		current = current.next;
	}
	return null;
}