Reverse Linked List II

LeetCode의 Reverse Linked List II 문제다.

Reverse Linked List II - LeetCode

첫 번째 노드부터 마지막 노드까지 오름차순 값을 가진 노드들의 연결 리스트를 주어진 범위만큼 뒤집어서 반환하는 것이다. 예를 들어 노드 1, 노드 2, 노드 3, 노드 4, 노드 5가 있을 때 2번째 노드부터 4번째 노드까지 뒤집어서 반환하라고 하면 노드 1, 노드 4, 노드 3, 노드 2, 노드 5 순서로 바뀌어서 반환되어야 한다.

노드의 값이 오름차순으로 주어진다는 조건은 무슨 의미가 있는지 모르겠는데 아마 연결 리스트가 잘 뒤집혔는지 확인하기 위한 수단인 것 같다. 생각해볼 수 있는 풀이 방법은 i 번째 노드부터 j 번째 노드까지 뒤집는다고 할 때 일단 i-1 번째 노드의 다음 노드를 j 번째 노드로 잇고 i 번째 노드가 j+1 번째 노드를 가리키도록 구현하는 것이다. 위의 예제에서는 2(i) 번째 노드부터 4(j) 번째 노드까지 뒤집기 때문에 1(i-1) 번째 노드가 다음 노드로 4(j) 번째 노드를 가리키고 2(i) 번째 노드는 5(j+1) 번째 노드를 가리키게 된다.

 

이때 맨 처음 노드부터 뒤집는 경우(i=1) i-1(0) 번째 노드는 존재하지 않을 수 있으므로 예외 처리가 필요하다. 그래서 맨 처음 노드부터 뒤집는 경우 j 번째 노드를 반환하도록 처리할 수 있다.

 

그리고 i 번째 노드부터 j 번째 노드까지는 파이썬의 동시 할당을 이용하여 다음 노드가 이전 노드를 가리키도록 변경하면서 어렵지 않게 진행할 수 있었다. 중요한 것은 노드를 뒤집는 것 자체보다는 뒤집힌 노드 주변의 노드들이 뒤집힌 노드들과 잘 연결될 수 있어야 한다는 것이다.

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        # 단 하나의 노드를 뒤집는 경우 별도의 작업이 필요하지 않음.
        if left == right:
            return head
        
        # 뒤집힐 맨 왼쪽 노드의 이전 노드까지 탐색.
        currentIndex = 1
        originHead = head
        leftBorderNode = None # i-1 번째 노드를 의미.
        while currentIndex < left:
            leftBorderNode = head
            head = head.next
            currentIndex += 1
        
        # 인덱스 기반으로 탐색하기 때문에 현재 노드가 뒤집힐 노드의 왼쪽 노드.
        leftNode = head

        # 뒤집힐 노드의 오른쪽 노드까지 탐색하면서 연결 뒤집기.
        prev = None
        while currentIndex <= right:
            # 현재 노드의 다음 노드(head.next)를 이전 노드(prev)로 설정.
            # 현재 노드(head)는 다음 노드(head.next)로 이동.
            # 이전 노드(prev)는 현재 노드(head)로 설정.
            # 위 과정은 파이썬의 기능으로 전부 동시에 실행가능.
            head.next, head, prev = prev, head.next, head
            currentIndex += 1

        # 만약 맨 마지막 노드까지 뒤집었다면 prev 변수는 맨 오른쪽 노드(j번째 노드)를 가리킴.
        rightNode = prev
        # head 변수는 j+1 번째 노드를 가리키고 있을것.
        rightBorderNode = head
        # i 번째 노드의 다음 노드로 j+1 번째 노드를 설정.
        leftNode.next = rightBorderNode
        
        # i-1번째 노드는 존재하지 않을 수 있으니 예외처리 후 j 번째 노드를 다음 노드로 설정.
        if leftBorderNode:
            leftBorderNode.next = rightNode
        # 만약 존재하지 않는다면 처음 노드부터 뒤집은 것이므로 뒤집은 후 첫번째 노드인 j 번째 노드를 반환.
        else:
            return rightNode
        
        # 처음에 저장해뒀던 첫번째 노드를 반환.
        return originHead