15. Reverse Linked List

• 연결 리스트를 뒤집어라

이 문제는 매우 일반적이면서도 활용도가 높은 문제로, 실무에서도 빈번하게 쓰인다.

1. 재귀 구조로 뒤집기 (40ms)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        
        def reverse(node: ListNode, prev: ListNode = None):
            if not node:
                return prev
            next, node.next = node.next, prev
            return reverse(next, node)
    
        return reverse(head)
        

• 다음 노드 next와 현재 노드 node를 파라미터로 지정한 함수를 계속해서 재귀 호출한다.

• node.next에는 이전 prev 리스트를 계속 연결해주면서 node가 None이 될 때까지 재귀 호출하면 마지막에는 백트래킹되면서 연결리스트가 거꾸로 연결된다.

  • 여기서 맨 처음에 리턴된 prev는 뒤집힌 연결 리스트의 첫 번째 노드가 된다.

2. 반복 구조로 뒤집기 (32ms)

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

• node.next를 이전 prev 리스트로 계속 연결하면서 끝날 때까지 반복한다.

• node가 None이 될 때 prev는 뒤집힌 연결 리스트의 첫 번째 노드가 된다.

• 반복 풀이의 경우 prev에 node를, node에 next를 별도로 셋팅하며, 이를 이용해 node가 None이 될 때까지 계속 while 반복문을 돌게 한다.

둘 다 비슷한 속도를 보이므로 둘 중 어느 방식으로 풀이하든 큰 문제는 없다. 다만 반복이 재귀에 비해 70% 수준의 메모리를 차지해 공간 복잡도는 좀 더 낮음 편이며, 실행 속도 또한 약간 더 빠른 편이다.