병합, 분할, 뒤에서 N번째 찾기
두 정렬 연결 리스트를 O(n)에 병합하고, 느린 포인터와 빠른 포인터로 중간에서 리스트를 분할하며, 뒤에서 n번째 노드를 찾습니다.
병합, 분할, 뒤에서 N번째 찾기은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
연결 리스트의 세 가지 핵심 패턴
이 수업에서는 더 어려운 문제를 구성하는 기본 요소로 매우 자주 등장하는 연결 리스트의 세 가지 기본 연산을 다룹니다. 정렬된 두 리스트 병합(병합 정렬과 K방향 병합에 사용), 중간 지점에서 리스트 분할(병합 정렬과 회문 판별에 사용), 뒤에서 n번째 노드 찾기(끝에서 n번째 노드 제거에 사용)입니다.
세 연산 모두 이미 배운 기법인 더미 헤드 노드, 느린 포인터와 빠른 포인터, 세심한 경계 추적에 의존합니다.
정렬된 두 리스트 병합
LeetCode 21의 '정렬된 두 리스트 병합'은 정렬된 두 연결 리스트가 주어졌을 때 하나의 정렬된 병합 리스트를 반환하는 문제입니다. 더미 헤드와 curr 꼬리 포인터를 사용합니다. 각 단계에서 두 리스트의 헤드를 비교하고 더 작은 노드를 curr에 연결합니다. 한 리스트를 모두 처리하면 다른 리스트의 나머지 부분을 연결합니다. 시간 복잡도는 O(n+m), 공간 복잡도는 O(1)입니다(제자리에서 포인터를 다시 연결).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2 # attach remaining nodes
return dummy.next
def build(arr):
d = ListNode(); c = d
for v in arr:
c.next = ListNode(v); c = c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
print(to_list(mergeTwoLists(build([1,2,4]), build([1,3,4]))))병합 과정을 단계별로 추적하기
mergeTwoLists([1,2,4], [1,3,4])를 추적해 보겠습니다. 1과 1을 비교하여 첫 번째 리스트의 1을 선택하고 첫 번째 리스트를 2로 이동합니다. 2와 1을 비교하여 두 번째 리스트의 1을 선택하고 두 번째 리스트를 3으로 이동합니다. 2와 3을 비교하여 첫 번째 리스트의 2를 선택하고 첫 번째 리스트를 4로 이동합니다. 4와 3을 비교하여 두 번째 리스트의 3을 선택하고 두 번째 리스트를 4로 이동합니다. 4와 4를 비교하여 첫 번째 리스트의 4를 선택하고 첫 번째 리스트를 None으로 이동합니다. 두 번째 리스트에 남은 4를 연결합니다. 결과는 [1,1,2,3,4,4]입니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
step = 0
while l1 and l2:
step += 1
if l1.val <= l2.val:
print(f'Step {step}: pick l1({l1.val})')
curr.next = l1; l1 = l1.next
else:
print(f'Step {step}: pick l2({l2.val})')
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
mergeTwoLists(build([1,2,4]),build([1,3,4]))느린 포인터와 빠른 포인터로 중간 지점 찾기
리스트를 중간 지점에서 분할하려면 느린 포인터와 빠른 포인터 패턴을 사용합니다. slow는 1단계씩 이동하고 fast는 2단계씩 이동합니다. fast가 None(또는 마지막 노드)에 도달하면 slow가 중간 지점에 있습니다. 길이가 짝수인 리스트에서는 두 중간 노드 중 첫 번째 노드에 도달하며, 이는 병합 정렬에서 리스트를 분할할 때 일반적으로 사용하는 방식입니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def split_at_mid(head):
'''Returns (first_half_head, second_half_head).'''
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
mid = slow.next # second half starts here
slow.next = None # sever the list
return head, mid
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
head=build([1,2,3,4,5])
first, second = split_at_mid(head)
print(to_list(first), to_list(second)) # [1,2,3] [4,5]연결 리스트의 병합 정렬
LeetCode 148 '리스트 정렬': 연결 리스트를 O(n log n) 시간과 O(log n) 공간에 정렬합니다. 방법은 리스트를 중간 지점에서 나누고, 각 절반을 재귀적으로 정렬한 다음 병합하는 것입니다. 연결 리스트의 병합 정렬이 자연스러운 이유는 중간 지점에서 나누는 데 O(n)이 걸리기 때문입니다(배열처럼 O(1)이 아님). 하지만 전체 복잡도는 여전히 O(n log n)이며, 스택 공간은 O(log n)만 사용합니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sortList(head):
if not head or not head.next:
return head
# Split
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# Recurse
left = sortList(head)
right = sortList(mid)
# Merge
dummy = ListNode(0)
curr = dummy
while left and right:
if left.val <= right.val:
curr.next = left; left = left.next
else:
curr.next = right; right = right.next
curr = curr.next
curr.next = left or right
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(sortList(build([4,2,1,3])))) # [1,2,3,4]뒤에서 N번째 노드 찾기
LeetCode 19 '리스트 끝에서 n번째 노드 제거': 한 번의 순회로 뒤에서 n번째 노드를 찾습니다. 정확히 n개의 노드만큼 떨어진 두 포인터를 사용합니다. fast를 slow보다 n만큼 앞서도록 이동합니다. 그런 다음 fast가 마지막 노드에 도달할 때까지 두 포인터를 함께 이동합니다. 이때 slow는 뒤에서 (n+1)번째 노드, 즉 제거할 노드의 이전 노드를 가리킵니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = dummy
for _ in range(n + 1): # advance fast n+1 steps
fast = fast.next
slow = dummy
while fast: # advance both until fast is None
slow = slow.next
fast = fast.next
slow.next = slow.next.next # remove nth node
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(removeNthFromEnd(build([1,2,3,4,5]), 2))) # [1,2,3,5]n번째 노드 제거에서 n+1단계가 필요한 이유
핵심적인 세부 사항은 더미 헤드에서 n이 아니라 n+1단계만큼 fast를 이동하는 것입니다. n+1단계를 이동하면 두 포인터가 모두 더미에서 시작했을 때 fast가 slow보다 n+1만큼 앞서게 됩니다. fast가 없음에 도달하면 slow는 없음보다 n+1개 위치 앞에 있습니다. 즉, 0부터 세었을 때 위치가 (length - n - 1)이거나, 목표 노드의 이전 노드에 도달한 것입니다. 따라서 slow.next = slow.next.next를 사용해 뒤에서 n번째 노드를 깔끔하게 삭제할 수 있습니다.
# Visual: list = [1,2,3,4,5], n=2
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
# After n+1=3 forward steps from dummy, fast=3
# dummy(slow) 1 2 3(fast) 4 5 None
# Advance both until fast=None:
# Step 1: slow=1, fast=4
# Step 2: slow=2, fast=5
# Step 3: slow=3, fast=None
# slow is at 3, slow.next=4 (the 2nd from end) -> delete
print('slow.next (to delete): 4')
print('Result: [1, 2, 3, 5]')두 연결 리스트의 교차점
LeetCode 160 '두 연결 리스트의 교차 노드': 두 리스트가 처음 교차하는 노드를 찾습니다. O(1) 공간을 사용하는 방법은 리스트마다 하나씩 두 포인터를 이동하는 것입니다. 포인터가 없음에 도달하면 다른 리스트의 헤드로 방향을 바꿉니다. 최대 len(A) + len(B)단계가 지나면 두 포인터가 이동한 총 거리가 같아지므로 교차 노드에서 만나게 됩니다. 교차점이 없다면 두 포인터 모두 없음에 도달합니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersectionNode(headA, headB):
a, b = headA, headB
while a is not b:
a = a.next if a else headB
b = b.next if b else headA
return a # None if no intersection
# Build: A: 4->1->\ B: 5->6->1->\ both -> 8->4->5
shared = [ListNode(v) for v in [8, 4, 5]]
shared[0].next = shared[1]; shared[1].next = shared[2]
A = ListNode(4); A.next = ListNode(1); A.next.next = shared[0]
B = ListNode(5); B.next = ListNode(6); B.next.next = ListNode(1); B.next.next.next = shared[0]
print(getIntersectionNode(A, B).val) # 8K개 정렬 리스트 병합(분할 정복)
LeetCode 23 'K개 정렬 리스트 병합': 정렬된 k개의 리스트가 주어졌을 때 하나의 리스트로 병합합니다. 최적의 방법은 분할 정복을 사용해 리스트 쌍을 반복해서 병합하고, 각 단계마다 리스트 수를 절반으로 줄이는 것입니다. 평균 길이가 n인 k개의 리스트가 있으면 순차적으로 병합할 때의 O(n k²)와 달리 O(n k log k) 시간이 걸립니다. 최소 힙을 사용하는 방법도 O(n k log k)입니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
def merge_two(l1, l2):
dummy = ListNode(0); curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1; l1 = l1.next
else:
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
if not lists: return None
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i+1] if i+1 < len(lists) else None
merged.append(merge_two(l1, l2))
lists = merged
return lists[0]
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
lists=[build([1,4,5]),build([1,3,4]),build([2,6])]
print(to_list(mergeKLists(lists))) # [1,1,2,3,4,4,5,6]홀짝 연결 리스트
LeetCode 328 '홀짝 연결 리스트': 홀수 인덱스 노드를 모두 먼저 배치한 다음 짝수 인덱스 노드를 배치합니다(인덱스는 1부터 시작). 방법은 홀수 체인과 짝수 체인이라는 두 개의 별도 연결 구조를 유지하고, 작업이 끝나면 이들을 연결하는 것입니다. 리스트를 한 번 순회하는 것만으로 충분하므로 O(n) 시간과 O(1) 공간이 필요합니다. 서로 다른 간격으로 두 포인터를 동시에 이동하는 좋은 예입니다.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head:
return head
odd = head
even = head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(oddEvenList(build([1,2,3,4,5])))) # [1,3,5,2,4]모든 패턴 종합하기
이 수업에서 배운 세 가지 패턴인 정렬된 리스트 병합, 중간 지점에서 나누기, 뒤에서 n번째 노드 찾기는 공통된 주제를 공유합니다. 추가 메모리를 사용하지 않고 위치를 추적하기 위해 여분의 포인터 변수를 사용하는 것입니다. 더미 헤드는 병합과 삭제를 단순하게 만들고, 느린 포인터와 빠른 포인터 사이의 간격은 특정 상대 위치를 고정하며, 한 포인터를 먼저 이동하면 원하는 간격이 만들어집니다.
면접에서는 코딩하기 전에 사용할 패턴을 먼저 말해 보십시오. "한 번의 순회로 뒤에서 n번째 노드를 찾기 위해 두 포인터 간격 기법을 사용하겠습니다."라고 말하면 체계적으로 사고하고 있음을 보여 줄 수 있습니다.
빠른 확인
이 수업에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 제대로 이해했는지 확인해 보십시오.
수업 요약
이 수업에서는 다음을 배웠습니다. 정렬된 두 리스트를 병합할 때 더미 헤드와 각 단계의 비교를 사용하면 O(n+m) 시간과 O(1) 공간이 필요합니다. 중간 지점에서 나눌 때는 빠른 포인터가 마지막으로 유효한 쌍에서 멈추도록 느린 포인터와 빠른 포인터를 사용합니다. 또한 뒤에서 n번째 노드를 찾을 때는 빠른 포인터를 n+1단계 먼저 이동해야 느린 포인터가 이전 노드에 도달합니다. 다음에는 스택과 큐를 만들고 이를 고전적인 면접 문제에 적용합니다.
자주 묻는 질문
“병합, 분할, 뒤에서 N번째 찾기” 강의는 무료인가요?
네 — “병합, 분할, 뒤에서 N번째 찾기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“병합, 분할, 뒤에서 N번째 찾기”에서 뭘 배우나요?
두 정렬 연결 리스트를 O(n)에 병합하고, 느린 포인터와 빠른 포인터로 중간에서 리스트를 분할하며, 뒤에서 n번째 노드를 찾습니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“병합, 분할, 뒤에서 N번째 찾기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 노드 클래스와 리스트 구성
- 연결 리스트 뒤집기
- Floyd 알고리즘으로 순환 탐지
- 병합, 분할, 뒤에서 N번째 찾기