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

문제

연결 리스트를 뒤집어라.

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

코드

"""
fixme
 https://leetcode.com/problems/reverse-linked-list/
 Q15. 역순 연결 리스트
 연결 리스트를 뒤집어라.
 입력 : 1 → 2 → 3 → 4 → 5 → NULL
 출력 : 5 → 4 → 3 → 2 → 1 → NULL
"""


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


class Solution:
    def reverseListRecur(self, head: ListNode) -> ListNode:
        def reverse(node: ListNode, prev: ListNode = None):
            if not node:
                return prev
            next, node.next = node.next, prev
            print(prev.val)
            return reverse(next, node)

        return reverse(head)

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

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

        return prev


Solution().reverseListRecur(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))))

풀이

재귀함수를 이용한 풀이에서 두번째 인자가 prev이고, 첫번째 인자 node가 없으면 그대로 prev 자체를 return한다. 계속 1 → prev, 2 → 1 → prev … 형태로 이어져서 헷갈릴 수 있는데 함수가 호출될 때 1 → prev, 2 → 1 → prev …자체가 prev가 된다. 그래서 결국 마지막에 5 → 4 → 3 → 2 → 1 → prev(None) 자체가 prev이고, 이것이 return된다.

아래 그림은 호출되면서 연결 리스트가 변하는 모습이다.

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