[Leetcode] 리트코드 - 역순 연결 리스트Ⅱ(reverse-linked-list-ii) 파이썬(python) 풀이

역순 연결 리스트 Ⅱ

문제

인덱스 m에서 n까지를 역순으로 만들어라. 인덱스 m은 1부터 시작한다.

입력
1→2→3→4→5→NULL, m = 2, n = 4

출력
1→4→3→2→5→NULL

코드

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if not head or m == n:
            return head

        root = start = ListNode(None)
        root.next = head

        for _ in range(m - 1):
            start = start.next

        end = start.next

        for _ in range(n - m):
            tmp, start.next, end.next = start.next, end.next, end.next.next
            start.next.next = tmp
        return root.next

l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(3)
l1.next.next.next = ListNode(4)
l1.next.next.next.next= ListNode(5)
l1.next.next.next.next.next = ListNode(None)
Solution().reverseBetween(l1, 2, 5)

풀이

start는 변경이 필요한 2의 바로 앞 지점인 1을 가리키게 하고 end는 start.next인 2로 지정한다. 그리고 head는 1인데, 그보다도 더 앞에 root를 만들어 head보다 이전에 위치시킨다. 나중에는 root.next를 최종 결과로 리턴하게 될 것이다.

이렇게 할당된 start와 end는 끝까지 변하지 않는다. 즉 1과 2로 마지막까지 유지되며, start와 end를 기준으로 반복하면서 역순으로 뒤집는다.

이 그림에서 2)부터가 반복하며 진행되는 부분이다. start.next를 tmp로 지정하고, start.next는 end.next가 된다. 그리고 end.next는 end.next.next로 한 칸 더 앞의 값을 끌어온다. 그리고 start.next.next를 tmp로 지정한다. 즉 이전에 start.next였던 노드를 배치하는 것과 동일하다.

다중할당 2번째 부분에서 start.next가 end.next를 가리키게 되어 기존의 start.next가 사라짐으로 먼저 tmp에 저장하고 나중에 start.next.next에 기존 start.next(tmp)를 엮어준다.

출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]