LeetCode 61(Rotate List, Python)

1. 문제 링크 

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

Rotate List - LeetCode

 

2. 문제 설명

• linked list의 head가 주어졌을 때, k번 오른쪽으로 회전한 linked list를 반환하기 
  • 예시1) head = [1,2,3,4,5], k = 2 → output = [4,5,1,2,3] 
    • k=1일 때, [2,3,4,5,1]이 되고, k=2일 때 [4,5,1,2,3] 
  • 예시2) head = [0,1,2], k=4 → output = [2,0,1] 

 

3. 처음 풀이

• 우선 한번만 오른쪽으로 회전시킨다고 가정하고 방법을 고민해보았다
  • head를 한 칸 먼저 앞으로 이동한 fast와 그보다 한칸 느린 slow를 두고
  • fast.next가 존재할 때까지 fast와 slow를 계속 next로 옮긴다.
    • 만약 head = [1,2,3,4,5]라 하면
    • 그러면 slow.next.val인 5가 앞으로 옮겨야 할 벨류가 되므로, 이를 val이라는 변수에 저장해두고,
    • slow.next는 None으로 변경하여, 끝부분에 있는 5를 잘라낸다.
    • 그리고 5를 val로 하는 ListNode(val)을 만들고, 그것의 next에 head를 붙여주는 구조로 짰다.
    • 즉 [1,2,3,4,5]에서 5를 잘라내고, ListNode(5)의 next에 [1,2,3,4]를 할당해주어 [5,1,2,3,4]를 만들었다.
  • k는 1보다 큰 경우도 있으므로, 1번 이동하는걸 함수로 짠 뒤, 이를 k번 반복하도록 for문을 돌렸다. 
    • 여기서 문제는, k가 너무 클 때, timelimit이 뜨는 것이었고, 
    • 회전을 하면 linked list의 노드 길이만큼 회전하면 결국 원점으로 돌아오므로,
      • node length를 계산해서, k % node_len만큼만 for문을 돌리도록 작성했다.
  • Runtime은 나쁘지 않았으나, 이것보다 좋은 풀이가 있을 것 같았고, 실제로도 더 간단하게 짤 수 있는 풀이가 있었다. (아래 작성)

# 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 head is None:
            return head

        if k == 0:
            return head

        if head.next is None:
            return head

        node_len= 0 
        temp = head

        while temp:
            temp = temp.next 
            node_len +=1

        def rotate_onetime(head):

            fast, slow = head.next, head
            val = fast.val

            while fast.next:
                fast = fast.next
                slow = slow.next
                val = slow.next.val

            slow.next = None 

            output = ListNode(val)
            output.next = head

            return output 

        if k % node_len == 0:
            return head

        for i in range(k % node_len):
            if i == 0:
                output = rotate_onetime(head)
            else:
                output = rotate_onetime(output)
        
        return output

 

4. 다른 풀이 

• 제로_콜라가 푼 풀이 
  • fast, slow를 둔 전략은 비슷했다.
  • 하지만, 더 현명하게 k번만큼 fast를 next로 이동시키고,
  • 그 다음부터 fast.next가 존재할때까지 fast, slow를 next로 이동시킨 후, 
    • fast.next에 head를 넣고, slow.next를 None으로 할당하여 꼬리자르기(필요없는 뒷부분)
  • 여기에서도 k가 node개수보다 큰 경우 노드 개수만큼 나눠주는 보정을 해주었다. 
• 굳히 함수를 짜서 그걸 n번 돌릴 필요 없이, fast, slow간격을 k만큼 둔것으로 아이디어가 더 좋다고 생각!

# 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

        fast = slow = head
        longer_than_cycle = False

        for i in range(k):
            if fast.next:
                fast = fast.next
            else:
                fast = head
                k = k % (i+1)
                longer_than_cycle = True
                break 
        
        if longer_than_cycle == True:
            for i in range(k):
                fast = fast.next
        
        while fast.next:
            fast = fast.next
            slow = slow.next
        
        fast.next = head
        result = slow.next
        slow.next = None
        return result

5. 배운 점

• linked list가 좀 더 익숙해지고 있다!