[LeetCode] 206. Reverse Linked List

# 문제 설명
Given the head of a singly linked list, reverse the list, and return the reversed list.

이 문제는 링크드 리스트가 주어졌을 때 주어진 리스트의 역순 리스트를 반환하는 문제이다.

 

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

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

Input: head = []
Output: []

 

이 문제를 보았을 때 쉽게 풀 수 있을 것이라 생각했지만 비효율적인 방법만 떠올랐다.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    	vals = []
        while head:
        	vals.append(head.val)
            head = head.next
        
        node = ListNode()
        ref_node = node
        
        for val in vals[::-1]:
        	node.next = ListNode(val)
            node = node.next
        return ref_node.next

 

하지만 이 방식은 너무 주먹구구식이었고 더 좋은 방식을 떠올리기 위해 curr, prev 두 리스트노드를 head, None으로 정의한 뒤, curr의 reference를 하나씩 뒤로 보내며 reference 앞쪽의 노드들을 다음 노드의 뒤로 붙이는 방식으로 해결할 수 있었다.

 

마지막으로, 아래와 같이 recursive한 방법으로도 풀 수 있다.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def _reverselist(head, tail=None):
            if head is None: return tail
            return _reverselist(head.next, ListNode(head.val, next=tail))
        return _reverselist(head)