92. Reverse Linked List II
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 đảo ngược một đoạn con liên tiếp của singly linked list, từ vị trí left -> right (theo chỉ số 1-based) và giữ nguyên các phần còn lại của danh sách. Đây là một biến thể của bài đảo ngược toàn bộ linked list, nhưng chỉ áp dụng cho một đoạn
Approach
prev để di chuyển node ngay trước vị trí left left -> right Minh họa bằng ví dụ
Với input: head = [1][2][3][4][5], left = 2, right = 4, ta cần đảo ngược đoạn [2][3][4] thành [4][3][2], kết quả là [1][4][3][2][5]
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 reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
14 if(!head || left === right) return head;
15 let dummy = new ListNode(0, head);
16 let prev = dummy;
17 for(let i =1; i < left; i++) {
18 prev = prev.next;
19 }
20
21 let curr = prev.next;
22 let next = null;
23 for(let i = 0; i< right - left; i++) {
24 next = curr!.next;
25 curr.next = next.next;
26 next.next = prev.next;
27 prev.next = next;
28 }
29
30 return dummy.next;
31};[left, right] bằng cách lần lượt chèn node tiếp theo lên đầu đoạn đảo ngược