題目敘述
Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4
Output: [2,0,1]
Constraints:
- The number of nodes in the list is in the range
[0, 500].
-100 <= Node.val <= 1000 <= k <= 2 * 10**9
題目翻譯
這題有一個序列 head 和一個常數 k，我們要將序列最後的 k 個元素輪替到前頭。類似將整個序列的所有元素往右移動 k 個。
解法解析
第一個迴圈先判斷出總長有多少，並且將最後一個節點連接到開頭形成一個迴圈。第二個迴圈再從起頭點往回找到新的結尾節點將其序列切斷，這邊要注意的地方是第二個迴圈的條件是 n - k % n - 1。
總長是 n，可以知道新的節點位置是在 n - k，但是如果今天 k >= n 的狀況呢？所以需要再加上 % n - 1。
解法範例
Go
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil {
return head
}
var oldTail *ListNode = head
var n int = 1
for oldTail.Next != nil {
oldTail = oldTail.Next
n++
}
oldTail.Next = head
var newTail *ListNode = head
for i := 0; i < n-k%n-1; i++ {
newTail = newTail.Next
}
newHead := newTail.Next
newTail.Next = nil
return newHead
}
JavaScript
const rotateRight = function (head, k) {
if (!head || !head.next) {
return head;
}
let oldTail = head,
n = 1;
while (oldTail.next) {
oldTail = oldTail.next;
n++;
}
oldTail.next = head;
let newTail = head;
for (let i = 0; i < n - (k % n) - 1; i++) {
newTail = newTail.next;
}
let newHead = newTail.next;
newTail.next = null;
return newHead;
};
Kotlin
class Solution {
fun rotateRight(head: ListNode?, k: Int): ListNode? {
if (head == null || head.next == null) return head
var oldTail: ListNode? = head
var count: Int = 1
while (oldTail?.next != null) {
oldTail = oldTail.next
count++
}
oldTail?.next = head
var newTail: ListNode? = head
for (i in 0 until count - k % count - 1) {
newTail = newTail?.next
}
val newHead: ListNode? = newTail?.next
newTail?.next = null
return newHead
}
}
PHP
class Solution
{
function rotateRight($head, $k)
{
if (is_null($head) || is_null($head->next)) {
return $head;
}
$oldTail = $head;
$n = 1;
while (!is_null($oldTail->next)) {
$oldTail = $oldTail->next;
$n++;
}
$oldTail->next = $head;
$newTail = $head;
for ($i = 0; $i < $n - $k % $n - 1; $i++) {
$newTail = $newTail->next;
}
$newHead = $newTail->next;
$newTail->next = null;
return $newHead;
}
}
Python
class Solution:
def rotateRight(self, head: ListNode | None, k: int) -> ListNode | None:
if head is None or head.next is None:
return head
old_tail: ListNode = head
n: int = 1
while old_tail.next:
old_tail = old_tail.next
n += 1
old_tail.next = head
new_tail: ListNode = head
for _ in range(n - k % n - 1):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None
return new_head
Rust
Swift
class Solution {
func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
var oldTail: ListNode? = head
var n: Int = 1
while oldTail?.next != nil {
oldTail = oldTail?.next
n += 1
}
oldTail?.next = head
var newTail: ListNode? = head
for _ in 0..<(n - k % n - 1) {
newTail = newTail?.next
}
let newHead: ListNode? = newTail?.next
newTail?.next = nil
return newHead
}
}