25. Reverse Nodes in k-Group
Tags:
Hard
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 đảo ngược các node của một linked-list theo từng nhóm k node liên tiếp. Nếu số node còn lại ở cuối danh sách nhỏ hơn k thì giữ nguyên thứ tự các node đó
Approach
Các bước cụ thể
Solution
1// Định nghĩa ListNode
2class ListNode {
3 val: number;
4 next: ListNode | null;
5 constructor(val?: number, next?: ListNode | null) {
6 this.val = (val===undefined ? 0 : val);
7 this.next = (next===undefined ? null : next);
8 }
9}
10
11function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
12 const dummy = new ListNode(0, head);
13 let pre: ListNode | null = dummy;
14
15 while (pre !== null) {
16 // Kiểm tra còn đủ k node không
17 let cur: ListNode | null = pre;
18 for (let i = 0; i < k; i++) {
19 cur = cur?.next || null;
20 if (cur === null) {
21 return dummy.next;
22 }
23 }
24
25 // Đảo ngược đoạn k node
26 const node = pre.next;
27 const nxt = cur?.next || null;
28 cur!.next = null; // Cắt đoạn k node
29
30 pre.next = reverse(node); // Đảo ngược đoạn node
31 node!.next = nxt; // Nối lại với phần còn lại
32
33 pre = node!; // Di chuyển pre sang cuối đoạn vừa đảo
34 }
35 return dummy.next;
36}
37
38// Hàm đảo ngược linked list
39function reverse(head: ListNode | null): ListNode | null {
40 let prev: ListNode | null = null;
41 let curr = head;
42 while (curr !== null) {
43 const next = curr.next;
44 curr.next = prev;
45 prev = curr;
46 curr = next;
47 }
48 return prev;
49}
50