【LeetCode】61. Rotate List 解答・解説【Python】

問題
1. 原文
2. 内容
方針
解答
1. 解答1：
補足・参考・感想

問題

原文

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]

1
2

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]

1
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⁹

内容

連結リストheadが与えられるので、k回だけ右回転で回転させてください。

制約

・リスト内のノードの数は0~500

・ノードの値は-100~100

・kは0~2*10^9

※正しくない可能性があります。

方針

・循環リストにする

・新しい末尾と先頭を取得する

・新たな先頭から新たな2番目の要素へのポインタを

・新たな末尾から新たな先頭へのポインタを切る

解答

解答1：

# 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:
            return head
        
        current = head
        length = 1
        #先頭から辿って末尾のポインタの値(val)を取得
        while current.next:
            current = current.next
            #遷移した数を記録
            length += 1
        #末尾のポインタのnextに先頭の値を保持することで循環リストを作成
        current.next = head

        #新しいheadに移動:例1では4-(2%4)=2　※kはrotationの回数
        k = length - (k%length)
        #rotationの回数(k)だけポインタを下げた後に指す要素が新たな末尾となる
        while k>0:
            #新たな末尾のポインタへ先頭から辿って遷移
            current = current.next
            k -= 1
        
        #新たな先頭を作成してheadを返す
        #末尾の要素の次が新たな先頭になるのでcurrent(末尾)のnextをnewheadに保持
        newhead = current.next
        #末尾のnextはNoneに変更
        current.next = None
        return newhead

# 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:

return head

current = head

length = 1

#先頭から辿って末尾のポインタの値(val)を取得

while current.next:

current = current.next

#遷移した数を記録

length += 1

#末尾のポインタのnextに先頭の値を保持することで循環リストを作成

current.next = head

#新しいheadに移動:例1では4-(2%4)=2　※kはrotationの回数

k = length - (k%length)

#rotationの回数(k)だけポインタを下げた後に指す要素が新たな末尾となる

while k>0:

#新たな末尾のポインタへ先頭から辿って遷移

current = current.next

k -= 1

#新たな先頭を作成してheadを返す

#末尾の要素の次が新たな先頭になるのでcurrent(末尾)のnextをnewheadに保持

newhead = current.next

#末尾のnextはNoneに変更

current.next = None

return newhead

補足・参考・感想

参考

前：2. Add Two Numbers

次：82. Remove Duplicates from Sorted List II

LeetCode 解答・解説記事一覧