연결 리스트(Linked List)가 주어졌을 때, 이를 역순으로 뒤집는 것이 이번 글의 목표입니다. 예를 들어 리스트가 1 → 3 → 5 → 7 형태라면, 뒤집힌 새로운 리스트는 7 → 5 → 3 → 1이 됩니다.
접근 방식: 재귀(Recursion) 활용
이 문제는 재귀 함수를 사용하면 간결하게 해결할 수 있습니다. 핵심 아이디어는 노드를 하나씩 순회하면서 각 노드의 next 포인터를 이전 노드를 가리키도록 변경하는 것입니다. 알고리즘은 다음과 같습니다.
solve(head, back)함수를 정의하여 리스트를 재귀적으로 뒤집습니다.- head가 존재하지 않으면 head를 그대로 반환합니다.
temp := head.next— 다음 노드를 임시 저장합니다.head.next := back— 현재 노드의 다음 포인터를 이전 노드로 변경합니다.back = head— 현재 노드를 '이전 노드'로 갱신합니다.- temp가 비어 있다면(마지막 노드에 도달했다면) head를 반환합니다.
head = temp— 다음 노드로 이동합니다.solve(head, back)을 재귀 호출합니다.
이 방식의 시간 복잡도는 O(n)이며, 재귀 호출 스택 때문에 공간 복잡도 역시 O(n)입니다.
예제 코드
아래 전체 구현 예제를 통해 동작 과정을 더 자세히 이해해 보겠습니다.
class ListNode:
def __init__(self, data, next=None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end="")
while ptr:
print(ptr.val, end=", ")
ptr = ptr.next
print(']')
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
return self.solve(head, None)
def solve(self, head, back):
if not head:
return head
temp = head.next
head.next = back
back = head
if not temp:
return head
head = temp
return self.solve(head, back)
list1 = make_list([1, 3, 5, 7])
ob1 = Solution()
list2 = ob1.reverseList(list1)
print_list(list2)
입력
list1 = [1, 3, 5, 7]
출력
[7, 5, 3, 1]
동작 원리 요약
reverseList 메서드는 초기 상태에서 back을 None으로 설정한 뒤 solve를 호출합니다. 재귀가 진행될수록 각 노드의 next 포인터가 앞쪽 노드를 가리키도록 바뀌고, 마지막 노드에 도달하면 해당 노드가 새로운 헤드가 되어 반환됩니다. 결과적으로 원래 리스트의 순서가 완전히 뒤집힌 새로운 연결 리스트를 얻게 됩니다.