Leetcode Python - 61. Rotate List

Leetcode #61 - Rotate List

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. linkedlist를 집중적으로 풀어보겠습니다.

리트코드의 문제 61 ‘Rotate List’을 파이썬으로 풀어 보도록 하겠습니다.

포인트는 k번씩 rotate를 하는 함수를 호출하는 방식으로 풀었습니다.

전체 코드는 아래와 같습니다.

class Solution:
    def rotateRight(self, head, k):
        if not k or not head or not head.next:
            return head
        node = head
        length = 0
        while node:
            node = node.next
            length += 1
        for _ in range(k%length):
            head = self.rotateOnce(head)
        return head
            
    def rotateOnce(self, head):
        dummy = ListNode(0)
        dummy.next = head
        prev = cur = dummy
        cur = cur.next
        
        while cur and cur.next:
            cur = cur.next
            prev = prev.next
        
        prev.next = None
        cur.next = head
        head = cur
        
        return head

시간복잡도는 O(kn) : 한번 rotate를 할 때마다 n씩 소요 * k번

공간복잡도는 O(1) : dummy LisNode를 생성

---

개선하기

포인트는 마지막과 첫번째 노드를 연결후 시작점과 끊어줄 지점을 구하는 것입니다.

class Solution:
    def rotateRight(self, head, k):
        if not k:
            return head
        elif not head:
            return None
        
        fast = last = head
        
        length = 1
        while last.next:
            last = last.next
            length += 1
        
        k = k%length
        for _ in range(length - k -1):
            fast = fast.next
        
        last.next = head
        head = fast.next
        fast.next = None
        return head

시간복잡도는 O(n) : 처음 while문에서 n번 loop + for문에서 n번 loop

공간복잡도는 O(1) : fast, last listNode 생성