86. Partition List
Tags:
Medium
Skills:
Linked List
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu chia lại linked list thành 2 phần: Tất cả node có giá trị nhỏ hơn x nằm trước các node có giá trị lớn hơn hoặc bằng x, đồng thời giữ nguyên thứ tự gốc của các node trong mỗi phần.
Approach
x (less)x (greater)Solution
1/**
2 * Definition for singly-linked list.
3 * class ListNode {
4 * val: number
5 * next: ListNode | null
6 * constructor(val?: number, next?: ListNode | null) {
7 * this.val = (val===undefined ? 0 : val)
8 * this.next = (next===undefined ? null : next)
9 * }
10 * }
11 */
12
13function partition(head: ListNode | null, x: number): ListNode | null {
14 let less_dummy = new ListNode(0);
15 let greater_dummy = new ListNode(0);
16
17 let less = less_dummy;
18 let greater = greater_dummy;
19
20 while (head) {
21 if (head.val < x) {
22 less.next = head;
23 less = less.next;
24 } else {
25 greater.next = head;
26 greater = greater.next;
27 }
28
29 head = head.next;
30 }
31
32 greater.next = null;
33 less.next = greater_dummy.next
34 return less_dummy.next;
35};