61. Rotate List
給定一個鏈表的頭節點，將該鏈表向右旋轉 k 個位置。
範例 1：
輸入：head = [1,2,3,4,5]，k = 2 輸出：[4,5,1,2,3]
Python
from typing import Optional
# Definition for singly-linked list.
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
# Calculate the length of the list
length = 1
current = head
while current.next:
current = current.next
length += 1
# Make the list circular
current.next = head
# Calculate the effective rotations needed
k = k % length
if k == 0:
current.next = None
return head
# Find the new tail (length - k - 1) and the new head (length - k)
new_tail = head
for _ in range(length - k - 1):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None
return new_head
16.56MB, 40ms
C++
/**
* 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;
}
// Calculate the length of the list
int length = 1;
ListNode* current = head;
while (current->next) {
current = current->next;
length += 1;
}
// Make the list circular
current->next = head;
// Calculate the effective rotations needed
k = k % length;
if (k == 0) {
current->next = nullptr;
return head;
}
// Find the new tail (length - k - 1) and the new head (length - k)
ListNode* new_tail = head;
for (int i = 0; i < length - k - 1; ++i) {
new_tail = new_tail->next;
}
ListNode* new_head = new_tail->next;
new_tail->next = nullptr;
return new_head;
}
};
15.32MB, 5ms
Javascript
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
if (!head || !head.next || k === 0) {
return head;
}
// Calculate the length of the list
let length = 1;
let current = head;
while (current.next) {
current = current.next;
length += 1;
}
// Make the list circular
current.next = head;
// Calculate the effective rotations needed
k = k % length;
if (k === 0) {
current.next = null;
return head;
}
// Find the new tail (length - k - 1) and the new head (length - k)
let new_tail = head;
for (let i = 0; i < length - k - 1; i++) {
new_tail = new_tail.next;
}
let new_head = new_tail.next;
new_tail.next = null;
return new_head;
};
51.05MB, 74ms
