연결 리스트(Linked List)가 주어졌을 때, 이를 역순으로 뒤집는 문제를 해결해 보겠습니다. 예를 들어 리스트가 2 → 4 → 6 → 8 형태라면, 뒤집은 후의 리스트는 8 → 6 → 4 → 2가 됩니다.
접근 방식: 재귀적 해결
이 문제는 재귀(recursion)를 활용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 리스트를 순회하면서 각 노드의 next 포인터가 이전 노드를 가리키도록 방향을 바꾸는 것입니다.
solve(head, back)이라는 재귀 함수를 정의하고, 다음 순서로 처리합니다.
- 기저 조건: head가 존재하지 않으면 그대로 head를 반환합니다.
- temp에 head.next(다음 노드)를 임시 저장합니다.
- head.next를 back(이전 노드)으로 변경하여 링크 방향을 반전시킵니다.
- back을 현재 head로 갱신합니다.
- temp가 비어 있다면(마지막 노드에 도달) head를 반환합니다.
- head를 temp로 이동시킨 뒤,
solve(head, back)을 재귀 호출합니다.
구현 예제
아래 코드는 연결 리스트 생성, 출력, 뒤집기 기능을 모두 포함한 완전한 예제입니다.
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):
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([5, 8, 9, 6, 4, 7, 8, 1])
ob1 = Solution()
list2 = ob1.reverseList(list1)
print_list(list2)
입력
[5, 8, 9, 6, 4, 7, 8, 1]
출력
[1, 8, 7, 4, 6, 9, 8, 5]
알고리즘 동작 원리
이 알고리즘은 세 개의 변수(head, back, temp)를 포인터처럼 활용합니다. 매 재귀 호출마다 현재 노드의 다음 포인터를 이전 노드로 연결하고, 한 칸씩 앞으로 진행합니다. 마지막 노드에 도달하면 해당 노드가 새로운 헤드가 되어 반환되며, 모든 재귀 호출이 종료되면 완전히 뒤집힌 리스트를 얻게 됩니다.
대안: 반복문을 이용한 구현
재귀 대신 반복문(iteration)을 사용하면 긴 리스트에서도 호출 스택 오버플로우 없이 안전하게 처리할 수 있습니다.
def reverseList(self, head):
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
복잡도 분석
- 시간 복잡도: O(n) — 리스트의 모든 노드를 정확히 한 번씩 방문합니다.
- 공간 복잡도: 재귀 방식은 호출 스택 때문에 O(n), 반복문 방식은 추가 메모리 없이 O(1)입니다.