연결 리스트 뒤집기
세 포인터를 재연결하는 방식으로 단일 연결 리스트를 반복적으로, 또 재귀적으로 뒤집으며 화이트보드 형식의 그림에서 각 단계를 추적합니다.
연결 리스트 뒤집기은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
리스트 뒤집기가 중요한 이유
연결 리스트 뒤집기는 코딩 면접에서 가장 자주 출제되는 질문 중 하나입니다. 노드를 놓치지 않고 포인터를 정확하게 조작하는 능력을 평가합니다. 이 변형 문제는 독립적인 문제로도 출제되고, 회문 감지, 리스트 재배치, k개 그룹 단위 뒤집기와 같은 더 큰 알고리즘의 하위 단계로도 등장합니다.
반복적 접근법은 세 포인터를 사용합니다: prev, curr, next_node. 재귀적 접근법은 호출 스택을 순회하는 방식으로 같은 로직을 표현합니다. 두 방법 모두 O(n) 시간에 동작하며, 반복적 접근법의 공간 복잡도는 O(1)입니다.
세 포인터를 이용한 반복적 뒤집기
반복적으로 뒤집을 때는 각 단계에서 다음 작업을 수행합니다. 리스트의 나머지 부분을 잃지 않도록 curr.next를 저장하고, curr.next가 prev를 뒤로 가리키도록 방향을 바꾸며, prev를 curr로 이동하고, curr를 저장해 둔 다음 노드로 이동합니다. curr가 None이 되면 반복이 끝나고 prev가 새로운 헤드가 됩니다.
유용한 암기법은 다음과 같습니다. 저장, 방향 전환, 이동, 이동.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # Save
curr.next = prev # Flip
prev = curr # Advance prev
curr = next_node # Advance curr
return prev # new head
# Test
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list(nodes[0])
while head:
print(head.val, end=' ') # 5 4 3 2 1
head = head.next단계별 추적
reverse_list가 1 -> 2 -> 3에서 어떻게 동작하는지 추적해 보겠습니다. 처음에는 prev=None, curr=1입니다. 1단계: 다음 노드 2를 저장하고, 1의 다음 포인터를 None으로 바꾸며, 이전 노드를 1, 현재 노드를 2로 설정합니다. 2단계: 다음 노드 3을 저장하고, 2의 다음 포인터를 1로 바꾸며, 이전 노드를 2, 현재 노드를 3으로 설정합니다. 3단계: 다음 노드 None을 저장하고, 3의 다음 포인터를 2로 바꾸며, 이전 노드를 3, 현재 노드를 None으로 설정합니다. 반복이 끝나면 이전 노드 3을 반환하며, 이는 3 -> 2 -> 1의 새로운 헤드입니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list_traced(head):
prev, curr = None, head
step = 0
while curr:
step += 1
next_node = curr.next
curr.next = prev
print(f'Step {step}: flipped {curr.val}.next -> {prev.val if prev else None}')
prev = curr
curr = next_node
return prev
nodes = [ListNode(i) for i in [1, 2, 3]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list_traced(nodes[0])
print('New head:', head.val) # 3재귀적 뒤집기
재귀 방식은 reverse_list(head.next)가 이미 뒤집힌 나머지 부분의 새로운 헤드를 반환한다고 가정합니다. 이제 head와 head.next 사이의 포인터만 뒤집으면 됩니다. head.next.next = head로 설정하여 기존의 두 번째 노드가 기존의 첫 번째 노드를 가리키게 하고, head.next = None으로 설정하여 기존의 정방향 연결을 끊습니다. 새로운 헤드는 기본 사례에서 시작해 위쪽으로 전달됩니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list_rec(head):
# Base case: empty or single node
if not head or not head.next:
return head
new_head = reverse_list_rec(head.next) # reverse suffix
head.next.next = head # former second node points back
head.next = None # sever forward link
return new_head
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverse_list_rec(nodes[0])
while head:
print(head.val, end=' ') # 4 3 2 1
head = head.next부분 리스트 뒤집기 (LeetCode 92)
LeetCode 92의 '연결 리스트 뒤집기 II'는 한 번의 순회로 왼쪽 위치부터 오른쪽 위치까지(1부터 시작하는 인덱스) 부분 리스트를 뒤집도록 요구합니다. 핵심은 부분 리스트 바로 앞의 노드를 찾는 것입니다. 더미 헤드를 사용하면 이 위치가 항상 유효합니다. 그런 다음 세 포인터 뒤집기를 (right - left)번 정확히 수행하고, 마지막으로 뒤집힌 구간을 주변 리스트에 다시 연결합니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseBetween(head, left, right):
dummy = ListNode(0, head)
pre = dummy
# Advance pre to node just before position 'left'
for _ in range(left - 1):
pre = pre.next
curr = pre.next
for _ in range(right - left):
next_node = curr.next
curr.next = next_node.next
next_node.next = pre.next
pre.next = next_node
return dummy.next
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverseBetween(nodes[0], 2, 4)
while head:
print(head.val, end=' ') # 1 4 3 2 5
head = head.nextK개 단위로 노드 뒤집기 (LeetCode 25)
LeetCode 25의 'K개 단위로 노드 뒤집기'는 연속된 k개의 노드로 이루어진 각 그룹을 뒤집습니다. 방법은 다음과 같습니다. k개의 노드가 남아 있는지 확인하고, 그렇지 않으면 해당 노드들을 그대로 둡니다. 반복 방식을 사용해 다음 k개의 노드를 뒤집은 후, 나머지 리스트를 재귀적으로 뒤집어 연결합니다. 시간 복잡도는 O(n)이며 재귀 호출 깊이는 O(n/k)로 유지됩니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseKGroup(head, k):
# Check if k nodes are available
curr, count = head, 0
while curr and count < k:
curr = curr.next
count += 1
if count < k:
return head # fewer than k nodes left, keep as-is
# Reverse k nodes
prev, curr = None, head
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# head is now the tail of the reversed group
head.next = reverseKGroup(curr, k)
return prev
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = reverseKGroup(nodes[0], 2)
while head:
print(head.val, end=' ') # 2 1 4 3 5
head = head.next회문 연결 리스트
LeetCode 234의 '회문 연결 리스트'는 연결 리스트가 회문인지 O(n) 시간과 O(1) 공간으로 확인하는 문제입니다. 전략은 느린 포인터와 빠른 포인터로 중간 지점을 찾고, 두 번째 절반을 제자리에서 뒤집은 다음, 두 절반을 노드 단위로 비교하고, 필요하다면 리스트를 복원하는 것입니다. 중간 지점 찾기와 뒤집기라는 두 가지 기본 기술을 하나로 연결하는 문제입니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def isPalindrome(head):
# Find mid
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Compare
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
def build(arr):
d = ListNode(0)
c = d
for v in arr:
c.next = ListNode(v)
c = c.next
return d.next
print(isPalindrome(build([1,2,2,1]))) # True
print(isPalindrome(build([1,2,3]))) # False반복 방식과 재귀 방식 비교
반복 방식의 뒤집기는 O(1) 공간을 사용하므로 일반적으로 더 선호됩니다. 재귀 방식의 뒤집기는 호출 깊이 때문에 O(n) 스택 공간을 사용하며, 매우 긴 리스트에서는 스택 오버플로를 일으킬 수 있습니다(파이썬의 기본 제한은 재귀 단계 약 1000개입니다).
면접에서는 먼저 반복 방식을 구현하여 공간 제약을 인식하고 있음을 보여 준 다음, 리스트 길이가 제한되어 있다면 더 간결한 대안으로 재귀 방식을 언급하는 것이 좋습니다.
import sys
print('Default recursion limit:', sys.getrecursionlimit())
# For a list of 10,000 nodes the recursive reversal would hit this limit
# Iterative reversal has no such constraint
# Increase if needed (use sparingly):
# sys.setrecursionlimit(20000)뒤집기에서 흔한 실수
뒤집기 관련 오류는 거의 모두 세 가지 실수에서 발생합니다. 첫째, 덮어쓰기 전에 다음 노드를 저장하지 않는 것입니다. curr.next = prev를 수행하기 전에 next_node를 저장하지 않으면 정방향 참조가 사라집니다. 둘째, prev를 반환하지 않는 것입니다. 반복문이 끝나면 curr는 None이지만 prev가 새로운 헤드입니다. 셋째, 재귀 기본 조건이 잘못된 것입니다. not head.next를 빠뜨리면 단일 노드 리스트를 처리하지 못하고 AttributeError가 발생합니다.
# Minimal correct iterative reversal — annotated against common bugs
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev, curr = None, head
while curr:
next_node = curr.next # BUG if omitted: lose rest of list
curr.next = prev
prev = curr
curr = next_node
return prev # BUG if you return curr: it is None
nodes = [ListNode(i) for i in [1, 2, 3]]
nodes[0].next = nodes[1]
nodes[1].next = nodes[2]
h = reverse_list(nodes[0])
while h:
print(h.val, end=' ') # 3 2 1
h = h.next연결 리스트 재정렬 (LeetCode 143)
LeetCode 143의 '연결 리스트 재정렬'은 L0 → L1 → L2 → ... → Ln을 L0 → Ln → L1 → Ln-1 → L2 → Ln-2로 O(n) 시간과 O(1) 공간에 재배열합니다. 해법은 세 단계로 이루어집니다. 중간 지점을 찾고, 두 번째 절반을 뒤집은 다음, 두 절반을 번갈아 연결합니다. 뒤집기를 익히면 겉보기에 복잡한 이 문제가 익숙한 도구를 조합하는 간단한 문제로 바뀝니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reorderList(head):
if not head or not head.next:
return
# Find mid
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow.next
slow.next = None
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Interleave
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
reorderList(nodes[0])
h = nodes[0]
while h:
print(h.val, end=' ') # 1 4 2 3
h = h.next요약: 뒤집기는 기본 구성 요소
연결 리스트 뒤집기는 최종 목표인 경우가 드뭅니다. 대신 다른 문제를 구성하는 기본 요소입니다. 회문 판별, K개 단위 뒤집기, 연결 리스트 재정렬, 위치 사이 구간 뒤집기는 모두 동일한 세 포인터 반복 패턴에 의존합니다. 이 패턴이 자동으로 떠오르면 더 높은 수준의 문제 구조에 사고력을 집중할 수 있습니다.
항상 뒤집기를 연습하여 2분 안에 기억만으로 작성할 수 있을 때까지 익히십시오. 연결 리스트 면접에서는 거의 항상 어떤 형태로든 등장합니다.
빠른 확인
이 수업에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.
수업 복습
이 수업에서는 다음을 배웠습니다. 반복 방식의 저장-뒤집기-전진-전진 패턴은 O(n) 시간과 O(1) 공간으로 리스트를 뒤집습니다. 재귀 방식은 나머지 부분이 이미 뒤집혔다고 가정하고 마지막 연결만 수정합니다. 또한 뒤집기는 회문 판별, 연결 리스트 재정렬, K개 단위 뒤집기에서 핵심 하위 단계로 사용됩니다. 다음으로 플로이드 알고리즘을 사용한 사이클 탐지를 살펴보겠습니다.
자주 묻는 질문
“연결 리스트 뒤집기” 강의는 무료인가요?
네 — “연결 리스트 뒤집기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“연결 리스트 뒤집기”에서 뭘 배우나요?
세 포인터를 재연결하는 방식으로 단일 연결 리스트를 반복적으로, 또 재귀적으로 뒤집으며 화이트보드 형식의 그림에서 각 단계를 추적합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“연결 리스트 뒤집기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.