# LeetCode Solution, Medium, 61. Rotate List

# [61. Rotate List](https://leetcode.com/problems/rotate-list/)

## 題目敘述

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

**Example 1:**

![rotate1.jpeg](https://cdn.hashnode.com/res/hashnode/image/upload/v1658278005506/vw7t4--bW.jpeg align="left")

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

**Example 2:**

![roate2.jpeg](https://cdn.hashnode.com/res/hashnode/image/upload/v1658278002862/sGSRviQ87.jpeg align="left")

    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

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

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

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

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

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

```rust
```

#### Swift

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