[leetcode] 206. 역순 연결 리스트 (Reverse Linked List)

들어가며

본 포스팅은 <파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 다루고 있습니다. 

문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 

 

포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다.

 

---

문제

Given the head of a singly linked list, reverse the list, and return the reversed list.

 

연결 리스트를 뒤집어라

 

 

입출력 예시

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

 

생각과정

head 노드 뒤에 prev를 두고 한칸씩 prev로 옮긴다... 라고 생각해는데 뭔가 생각대로 되질 않았다.

고민의 흔적들 중 일부

결국 해설을 봤는데 놀랍게도 접근방식이 비슷했다!!! 단지 구현방법을 몰랐던 것 뿐. 뿌듯하니까 해설의 코드를 보자

 

풀이

첫번째 방법

def reverseList(head: ListNode) -> ListNode:
    node, prev = head, None

    while node:
        next, node.next = node.next, prev
        prev, node = node, next

    return prev

내가 생각한 접근방식이 거의 근접했는데, 차이는 노드 next를 이용해서 노드 node.next와의 연결이 끊기지 않게 하는 점이다.

코드는 간결하지만 이해하는 부분이 역시나 시각적으로 표현해야 이해가 됐는데, 사고력을 키우기 위해서 이번에는 글로 써보겠다.

 

우선, 다중할당 형식으로 코드를 보는 것보다 일렬로 쭉 나열하는게 이해하기 쉽기 때문에 아래 코드로 보자.

next = node.next
node.next = prev
prev = node
node = next

 

어? 이런 형태를 어디서 많이 봤다. java에서 a와 b를 스왑하는 간단한 코드를 이런 방식으로 썼던 것 같다.

a = 1
b = 2

print(a, b) # 1 2

temp = a
a = b
b = a

print(a, b) # 2 1

확실히 비슷하다!

 

 

 

그럼 다시 원래의 코드를 살펴보자

next = node.next
node.next = prev
prev = node
node = next

 

next에 우선 node.next를 담아준다. node.next는 두개가 됐다. 이걸 연결리스트 방식으로 말하면 node.next의 참조값을 잃어버리지 않게 next를 연결해줬다고 한다.

그럼 이제 node.next에 None인 prev를 담아준다. 이걸로 node.next와 node.next.next와의 연결이 끊어졌다.

prev에 node(현재 head)를 담아준다. prev와 node.next를 연결해준 것이다.

마지막으로 node(현재 head)에 node.next인 next를 담아준다. 

 

첫번째를 진행하고나서 완성된 연결리스트를 그림으로 표현하면 다음과 같다.

이 방식을 while문으로 계속 반복하면 최종적으로 역순 정렬된 연결리스트를 return 하게 된다.

 

 

그럼 이번에는 해설에서 나온 재귀 호출로 푸는 두번째 방식을 보자.

def reverseList(head: ListNode) -> ListNode:
    def reverse(node: ListNode, prev: ListNode):
        # node가 없을 때, null을 반환
        if not node:
            return prev

        # next -> 다음노드, 다음노드 -> None
        next, node.next = node.next, prev

        return reverse(next, node)
    return reverse(head)

 

되게 복잡해보이고 헷갈리지만 그림을 그려서 한단계씩 나아가다보면 결국 맨 앞의 node를 하나씩 뒤로 옮겨주는 과정일 뿐이다. 

 

재귀 호출에 익숙해지니 그림을 그리기 더 편해졌다! 

보여주기 민망한건 작게...

 

아무튼 최종적으로 역순 배열된 리스트를 return해서 해결!! 

---

 

마치며

연결리스트는 시각적인 자료를 보면서 구조를 제대로 파악해야 수월하게 풀 수 있을 것 같다. 그래서 그림으로 직접 그려보는게 도움이 많이 된다. 그냥 라이브러리 쓰면 안되나요...