LeetCode 61: Rotate List (Cycle + Cut at New Tail)
LeetCode 61Linked ListTwo PointersToday we solve LeetCode 61 - Rotate List.
Source: https://leetcode.com/problems/rotate-list/
English
Problem Summary
Given the head of a linked list, rotate the list to the right by k places.
Key Insight
Rotating right by k is equivalent to moving the last k % n nodes to the front, where n is list length. We can connect tail to head to form a cycle, then cut at the new tail.
Brute Force and Limitations
Doing one-step rotation k times costs O(k*n), which is too slow when k is large (for example up to 2 * 109 in some variants).
Optimal Algorithm Steps
1) Handle edge cases: empty list, single node, or k == 0.
2) Traverse once to get length n and tail.
3) Compute shift = k % n; if shift == 0, return original head.
4) Connect tail.next = head to build a cycle.
5) New tail is the (n - shift - 1)-th node from head.
6) New head is newTail.next; cut by setting newTail.next = null.
Complexity Analysis
Time: O(n).
Space: O(1).
Common Pitfalls
- Forgetting modulo, causing unnecessary long rotations.
- Off-by-one when finding newTail.
- Forgetting to break the cycle, creating an infinite loop list.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
int n = 1;
ListNode tail = head;
while (tail.next != null) {
tail = tail.next;
n++;
}
int shift = k % n;
if (shift == 0) {
return head;
}
tail.next = head;
int stepsToNewTail = n - shift - 1;
ListNode newTail = head;
for (int i = 0; i < stepsToNewTail; i++) {
newTail = newTail.next;
}
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil || k == 0 {
return head
}
n := 1
tail := head
for tail.Next != nil {
tail = tail.Next
n++
}
shift := k % n
if shift == 0 {
return head
}
tail.Next = head
stepsToNewTail := n - shift - 1
newTail := head
for i := 0; i < stepsToNewTail; i++ {
newTail = newTail.Next
}
newHead := newTail.Next
newTail.Next = nil
return newHead
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (!head || !head->next || k == 0) return head;
int n = 1;
ListNode* tail = head;
while (tail->next) {
tail = tail->next;
n++;
}
int shift = k % n;
if (shift == 0) return head;
tail->next = head;
int stepsToNewTail = n - shift - 1;
ListNode* newTail = head;
while (stepsToNewTail--) {
newTail = newTail->next;
}
ListNode* newHead = newTail->next;
newTail->next = nullptr;
return newHead;
}
};# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head or not head.next or k == 0:
return head
n = 1
tail = head
while tail.next:
tail = tail.next
n += 1
shift = k % n
if shift == 0:
return head
tail.next = head
steps_to_new_tail = n - shift - 1
new_tail = head
for _ in range(steps_to_new_tail):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None
return new_head/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var rotateRight = function(head, k) {
if (!head || !head.next || k === 0) return head;
let n = 1;
let tail = head;
while (tail.next) {
tail = tail.next;
n++;
}
const shift = k % n;
if (shift === 0) return head;
tail.next = head;
let stepsToNewTail = n - shift - 1;
let newTail = head;
while (stepsToNewTail > 0) {
newTail = newTail.next;
stepsToNewTail--;
}
const newHead = newTail.next;
newTail.next = null;
return newHead;
};中文
题目概述
给定链表头结点 head，将链表向右旋转 k 个位置并返回新头结点。
核心思路
向右旋转 k 次，本质上只与 k % n 有关（n 为链表长度）。先把尾结点连回头结点形成环，再在“新尾巴”处断开即可。
基线解法与不足
每次旋转 1 位并重复 k 次，时间复杂度是 O(k*n)。当 k 很大时非常低效。
最优算法步骤
1）处理边界：空链表、单节点、k == 0。
2）遍历一次得到长度 n 和尾结点。
3）计算 shift = k % n；若为 0 直接返回。
4）执行 tail.next = head，把链表变成环。
5）新尾结点是从头开始第 n - shift - 1 个节点。
6）新头结点为 newTail.next，然后将 newTail.next = null 断开。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
常见陷阱
- 忘记取模，导致无意义重复旋转。
- 找新尾巴时下标偏一位（off-by-one）。
- 忘记断环，返回后链表会变成无限循环。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
int n = 1;
ListNode tail = head;
while (tail.next != null) {
tail = tail.next;
n++;
}
int shift = k % n;
if (shift == 0) {
return head;
}
tail.next = head;
int stepsToNewTail = n - shift - 1;
ListNode newTail = head;
for (int i = 0; i < stepsToNewTail; i++) {
newTail = newTail.next;
}
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil || k == 0 {
return head
}
n := 1
tail := head
for tail.Next != nil {
tail = tail.Next
n++
}
shift := k % n
if shift == 0 {
return head
}
tail.Next = head
stepsToNewTail := n - shift - 1
newTail := head
for i := 0; i < stepsToNewTail; i++ {
newTail = newTail.Next
}
newHead := newTail.Next
newTail.Next = nil
return newHead
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (!head || !head->next || k == 0) return head;
int n = 1;
ListNode* tail = head;
while (tail->next) {
tail = tail->next;
n++;
}
int shift = k % n;
if (shift == 0) return head;
tail->next = head;
int stepsToNewTail = n - shift - 1;
ListNode* newTail = head;
while (stepsToNewTail--) {
newTail = newTail->next;
}
ListNode* newHead = newTail->next;
newTail->next = nullptr;
return newHead;
}
};# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head or not head.next or k == 0:
return head
n = 1
tail = head
while tail.next:
tail = tail.next
n += 1
shift = k % n
if shift == 0:
return head
tail.next = head
steps_to_new_tail = n - shift - 1
new_tail = head
for _ in range(steps_to_new_tail):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None
return new_head/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var rotateRight = function(head, k) {
if (!head || !head.next || k === 0) return head;
let n = 1;
let tail = head;
while (tail.next) {
tail = tail.next;
n++;
}
const shift = k % n;
if (shift === 0) return head;
tail.next = head;
let stepsToNewTail = n - shift - 1;
let newTail = head;
while (stepsToNewTail > 0) {
newTail = newTail.next;
stepsToNewTail--;
}
const newHead = newTail.next;
newTail.next = null;
return newHead;
};
Comments