61. Rotate List

Description

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⁹

Submitted Code

# 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 or not head.next or k == 0:
            return head
        
        curr = head
        length = 0
        while curr:                 # 전체 길이 구하기
            length += 1
            curr = curr.next
        
        k = k % length              # 불필요한 회전 줄이기
        if k == 0:
            return head
            
        dummy = ListNode(0, head)   # 맨 앞에 더미 노드 생성
        fast, slow = dummy, dummy
        
        for _ in range(k):          # fast를 k만큼 먼저 보냄
            fast = fast.next

        while fast.next:            # fast가 끝에 도달할 때까지 slow와 함께 이동
            fast = fast.next
            slow = slow.next
            
        new_head = slow.next        # 새 시작점 설정
        fast.next = dummy.next      # 리스트의 끝을 기존 머리에 연결
        slow.next = None            # 새로운 꼬리부분 끊기
        
        return new_head

Runtime: 0 ms | Beats 100.00%
Memory: 19.44 MB | Beats 14.63%

포인터 두 개와 더미 노드를 이용해서 자를 부분을 찾은 후 이어 붙이는 방법을 썼다.

Other Solutions

1st

class Solution(object):
    def rotateRight(self, head, k):
        if not head or k == 0:
            return head

        length = 1
        tail = head
        while tail.next:
            tail = tail.next
            length += 1

        k = k % length
        if k == 0:
            return head

        tail.next = head  # Make it circular
        steps_to_new_head = length - k
        new_tail = tail
        while steps_to_new_head:
            new_tail = new_tail.next
            steps_to_new_head -= 1

        new_head = new_tail.next
        new_tail.next = None
        return new_head

time complexity: 𝑂(𝑛)
space complexity: 𝑂(1)

연결 리스트 시작과 끝을 연결해서 원형 리스트처럼 만드는 방법이다.