143. Reorder 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
Approach
Giải thuật chi tiết
Time and space complexity
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
13/**
14 Do not return anything, modify head in-place instead.
15 */
16function reorderList(head: ListNode | null): void {
17 if (!head || !head.next || !head.next.next) return;
18
19 // Step 1: Find a half behind
20 let slow: ListNode | null = head;
21 let fast: ListNode | null = head;
22
23 while (fast && fast.next) {
24 slow = slow.next;
25 fast = fast.next.next;
26 }
27
28 // Step 2: Reverse half behind
29 let prev: ListNode | null = null;
30 let curr: ListNode | null = slow.next;
31 slow.next = null;
32
33 while (curr) {
34 let temp = curr.next;
35 curr.next = prev;
36 prev = curr;
37 curr = temp;
38 }
39
40 // Step 3: Merge
41 let first: ListNode | null = head;
42 let second: ListNode | null = prev;
43 while (second) {
44 let temp1 = first.next;
45 let temp2 = second.next;
46
47 first.next = second;
48 second.next = temp1;
49
50 first = temp1;
51 second = temp2;
52 }
53};