Daily Leetcoding Challenge 92. Reverse Linked List II

오늘도 준비운동 삼아한 문제 풀고 시작하려고 했는데.. 꼬여서 오전 내내 풀게 된 문제 😇 잘못된 접근 방법을 쓰고 있다면 빠르게 피벗 하는 것도 좋은 전략이다.

https://leetcode.com/problems/reverse-linked-list-ii

Reverse Linked List II - LeetCode

직관

index가 0부터 시작하고, 링크드 리스트에서 left, right 사이의 노드의 순서를 뒤집은 링크드 리스트를 리턴해야 한다.

left-1 만큼 커서를 이동한 뒤 right까지 reverse를 하고 head, tail을 기존 연결리스트와 연결하려고 했는데, 잘 안 됐다 😇 결국 솔루션을 봤는데, right - left 횟수만큼 reverse를 반복하면 되는 거였다.

reverse 할 때 dummy 노드를 만들어두면 좋은 점은 left가 1일 때(첫 번째 노드부터 reverse 할 때)도 예외처리 없이 dummy.next를 head로 리턴할 수 있어서 좋다.

 

접근법

dummy ListNode를 생성하고, dummy.next = head로 설정한다.

prev = dummy, cur = head로 초기화한다

cur 커서를 left 번 옮긴다

right - left 번 동안 노드를 reverse 한다. 노드를 하나씩 reverse 하는게 익숙하지 않아서 그림을 첨부해 봤다. 👍

알고리즘 설명

dummy.next를 리턴한다.

복잡도

이 알고리즘의 경우 링크드 리스트를 한 번만 순회하면서 left, right 사이의 노드들을 뒤집기 때문에 시간 복잡도는 O(n)이 된다. 그리고 공간 복잡도는 O(1)이다.

 

코드

class Solution(object):
    def reverseBetween(self, head, left, right):
        """
        :type head: ListNode
        :type left: int
        :type right: int
        :rtype: ListNode
        """
        dummy = ListNode()
        dummy.next = head
        
        cur, prev = head, dummy
        for i in range(0, left - 1):
            cur = cur.next
            prev = prev.next
        
        for i in range(0, right - left):
            next = cur.next
            cur.next = next.next
            next.next = prev.next
            prev.next = next

        return dummy.next