파이썬 알고리즘 인터뷰 15번 역순 연결 리스트(리트코드 206번)

Problem

LeetCode - The World's Leading Online Programming Learning Platform

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

Solution

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None

        first_node, _ = self.reverse(head)
        return first_node

    def reverse(self, node: ListNode):
        if node.next is None:
            reverse_first = ListNode(node.val)
            return reverse_first, reverse_first

        reverse_first, prev = self.reverse(node.next)
        current_node = ListNode(node.val)
        prev.next = current_node

        return reverse_first, current_node

재귀를 이용하여 주어진 연결 리스트의 제일 마지막 노드로 이동한 뒤 제일 마지막 노드부터 차례대로 올라오면서 새로운 연결 리스트를 만들어서 역순으로 정렬하였다.

Reference

파이썬 알고리즘 인터뷰