攻城獅
Not a programmer 不工程的攻城獅

Not a programmer 不工程的攻城獅

LeetCode Solution, Medium, 61. Rotate List

輪替列表

攻城獅's photo
攻城獅
·Jul 20, 2022·

Subscribe to my newsletter and never miss my upcoming articles

Play this article

61. Rotate List

題目敘述

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

rotate1.jpeg

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

roate2.jpeg

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
    }
}

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this

Impressum

As smiple as possible