[LeetCode] 206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/

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

---

접근 방법 (iteration)

• 연결 리스트를 순회하는 포인터 하나와 역순 리스트의 head 가 될 포인터 하나를 잡고, 반복문을 통해 순회하면서 역순 리스트를 채운다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # iteration
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        rev = None
        while head:
            rev, rev.next, head = head, rev, head.next
        return rev

• node 포인터가 head 부터 순차적으로 리스트를 순회하고, rev 포인터를 이용하여 순회한 노드들을 역순으로 연결한다.

---

접근 방법 (recursion)

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

• 재귀 함수를 만들어 역순 리스트를 작성하는 방법도 있다.

• 현재 노드와 이전 노드를 파라미터로 받는 재귀 함수를 만들고, 매 재귀마다 현재 노드의 node.next 를 이전 노드로 바꿔준 다음, 현재 노드의 다음 노드가 None 이면 그 노드를 head로 하는 새로운 연결 리스트를 만들어 반환한다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # recursion
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse_recursive(prev_node: Optional[ListNode], node: Optional[ListNode]) -> Optional[ListNode]:
            if node:
                rev = reverse_recursive(node, node.next)
                node.next = prev_node
            else:
                rev = prev_node
            return rev
        rev = reverse_recursive(None, head)
        return rev

• 하나의 함수 안에서 반복문으로 해결하는 방법보다 시간적, 공간적 소모가 더 큰 것을 확인할 수 있다.

---

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
   # recursion2
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse_recursive(prev_node: Optional[ListNode], node: Optional[ListNode]) -> Optional[ListNode]:
            if node:
                next_node, node.next = node.next, prev_node
                return reverse_recursive(node, next_node)
            else:
                return prev_node
        
        return reverse_recursive(None, head)

• 책을 참고하여 재귀 함수를 조금 더 깔끔하게 정리해보았다.