61. Rotate List

題目敘述

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 <= 100
• 0 <= k <= 2 * 10**9

題目翻譯

這題有一個序列 head 和一個常數 k，我們要將序列最後的 k 個元素輪替到前頭。類似將整個序列的所有元素往右移動 k 個。

解法解析

第一個迴圈先判斷出總長有多少，並且將最後一個節點連接到開頭形成一個迴圈。第二個迴圈再從起頭點往回找到新的結尾節點將其序列切斷，這邊要注意的地方是第二個迴圈的條件是 n - k % n - 1。

總長是 n，可以知道新的節點位置是在 n - k，但是如果今天 k >= n 的狀況呢？所以需要再加上 % n - 1。

解法範例

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
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

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
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

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
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

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @param Integer $k
     * @return ListNode
     */
    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

# 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: ListNode | None, k: int) -> ListNode | None:
        # base cases
        if head is None or head.next is None:
            return head

        # close the linked list into the ring
        old_tail: ListNode = head
        n: int = 1
        while old_tail.next:
            old_tail = old_tail.next
            n += 1
        old_tail.next = head

        # find new tail : (n - k % n - 1)th node
        # and new head : (n - k % n)th node
        new_tail: ListNode = head
        for _ in range(n - k % n - 1):
            new_tail = new_tail.next
        new_head = new_tail.next

        # break the ring
        new_tail.next = None

        return new_head

Rust

Swift

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
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
    }
}