Leetcode - 92. Reverse Linked List II

문제

주어진 범위 내의 링크드 리스트를 뒤집는 문제이다.

정답

다른 링크드 리스트 문제들과 비슷하게 두 가지로 접근이 가능하다.

1. 바꾸고자 하는 범위를 추출한 다음, 새로운 리스트를 생성해 원래 리스트에 이어붙인다.

2. 리스트를 순회하면서 바로 이어붙인다.

어쨌든 전체 리스트를 2번 순회해야 하기 때문에, 시간복잡도는 동일하지만 공간복잡도 면에서 두번째 방법이 유리하다. 사실 항상 두번째 방법이 유리할 수밖에 없긴 하다.

문제 해결 아이디어는 다음과 같다. 시작과 끝에 해당하는 노드를 저장한다. 그 다음 리스트를 순회하면서, end 가 바라보는 다음 노드를 start 의 다음 노드로, end.next 가 바라보는 다음 노드는 end 의 다음 노드로 지정한다. 이때 현재 이동하고 있는 리스트를 저장해둬야 하기 때문에 temp 변수를 별도로 지정해 사용한다.

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        # early terminate
        if not head or left == right:
            return head

        # "root" and "start" should be the same, to return start of the linked list.
        root = start = ListNode()
        # Acutally, "start" starts from head.
        start.next = head

        # before left index, find start and end nodes
        for _ in range(left - 1):
            start = start.next
        end = start.next

        # now reverse nodes between left <= idx <= right
        for _ in range(right - left):
            temp, start.next, end.next = start.next, end.next, end.next.next
            start.next.next = temp

        return root.next