61. Rotate List

[zeikar]

Problem link

https://leetcode.com/problems/rotate-list/

Problem Summary

링크드 리스트를 k번 회전시키는 문제.

Solution

그냥 말 그대로 k번 회전시키면 된다. k가 크므로 먼저 리스트의 길이를 구해서 mod 연산으로 줄여줘야 하고, 회전 후 맨 뒤로 이동해서 연결을 끊어준 후 끊어진 tail과 head를 연결하면 된다.

Source Code

# Definition for singly-linked list.
from typing import Optional


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 None

        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next

        if k % length == 0:
            return head

        # rotate
        curr = head
        for _ in range(length - k % length - 1):
            curr = curr.next
        new_head = curr.next
        curr.next = None

        # connect
        curr = new_head
        while curr.next:
            curr = curr.next
        curr.next = head

        return new_head