61. Rotate 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 rotate một singly linked list sang phải k lần. Tức là, mỗi lần xoay, node cuối cùng sẽ được di chuyển lên đầu danh sách. Nếu k lớn hơn độ dài danh sách, chỉ cần thực hiện k mod n vòng xoay, với n là độ dài danh sách
Approach
k = k mod n . Nếu k = 0, return head vì danh sách không thay đổi gì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 rotateRight(head: ListNode | null, k: number): ListNode | null {
14 if (!head || !head.next) return head;
15
16 let len = 1;
17 let fast = head;
18 while (fast.next) {
19 fast = fast.next;
20 len++
21 }
22
23 k = k % len
24 if (k === 0) return head;
25
26 let slow = head;
27 for (let i = 0; i < len - k - 1; i++) {
28 slow = slow.next;
29 }
30
31x
32 let new_head = slow.next;
33 slow.next = null;
34 fast.next = head;
35 return new_head;
36};len - k - 1 ?Giá trị len - k - 1 xuất hiện trong vòng lặp là để xác định node đứng ngay trước node mới sẽ trở thành head sau khi xoay phải k lần
Giải thích chi tiêt:
len - k ) tính từ đầu (vì nếu đếm từ 0 thì node đầu là vị trí 0)len - k - 1 ) sau đóslow.next = null để tách danh sách tại đây.slow.next trước khi bị tách) sẽ là node mới (new head).Ví dụ:
Danh sách có 5 node: 1 → 2 → 3 → 4 → 5, k = 2
len = 5, k = 2, vị trí cần cắt là 5 - 2 - 1 = 2 (node giá trị 3, vị trí thứ 2 nếu đếm từ 0).Tóm lại, len - k - 1 là để tìm node ngay trước vị trí cần cắt, đảm bảo việc xoay danh sách đúng logic.