이미지 로딩 중...
AI Generated
2025. 11. 7. · 8 Views
투 포인터로 연결 리스트 문제 완벽 정복하기
연결 리스트의 중간 노드 찾기, 사이클 탐지, 두 리스트 교차점 찾기 등 실무에서 자주 마주치는 문제들을 투 포인터 기법으로 효율적으로 해결하는 방법을 배웁니다. 시간 복잡도 O(n), 공간 복잡도 O(1)로 최적화된 솔루션을 제공합니다.
목차
- 투 포인터 기법 기초
- 연결 리스트 중간 노드 찾기
- 사이클 탐지하기
- 사이클 시작점 찾기
- 끝에서 N번째 노드 찾기
- 두 연결 리스트 교차점 찾기
- 연결 리스트 회문 검사
- 연결 리스트를 두 부분으로 분할하기
1. 투 포인터 기법 기초
시작하며
여러분이 연결 리스트 문제를 풀 때 "배열이었다면 쉬웠을 텐데..."라고 생각해본 적 있나요? 배열은 인덱스로 바로 접근할 수 있지만, 연결 리스트는 처음부터 하나씩 따라가야 하죠.
특히 중간 지점을 찾거나, 끝에서 몇 번째 노드를 찾는 문제는 까다롭게 느껴집니다. 전통적인 방법으로는 리스트를 두 번 순회해야 합니다.
첫 번째로 전체 길이를 세고, 두 번째로 원하는 위치까지 이동하는 것이죠. 이는 비효율적일 뿐만 아니라, 사이클이 있는 리스트에서는 무한 루프에 빠질 수도 있습니다.
바로 이럴 때 필요한 것이 투 포인터 기법입니다. 서로 다른 속도로 움직이는 두 개의 포인터를 사용하면, 단 한 번의 순회로 복잡한 문제들을 해결할 수 있습니다.
추가 메모리도 거의 사용하지 않으면서 말이죠.
개요
간단히 말해서, 투 포인터 기법은 두 개의 포인터를 서로 다른 속도나 시작 위치로 움직이면서 연결 리스트를 탐색하는 알고리즘 패턴입니다. 가장 일반적인 형태는 "느린 포인터(slow)"와 "빠른 포인터(fast)"를 사용하는 것입니다.
느린 포인터는 한 번에 한 칸씩, 빠른 포인터는 한 번에 두 칸씩 이동합니다. 이 속도 차이가 만들어내는 관계를 활용하면, 중간 지점 찾기, 사이클 탐지, N번째 노드 찾기 같은 문제들을 단 한 번의 순회로 해결할 수 있습니다.
기존에는 리스트의 길이를 먼저 계산하고 다시 순회했다면, 이제는 두 포인터의 상대적 위치를 이용해 한 번에 답을 찾을 수 있습니다. 시간 복잡도는 여전히 O(n)이지만, 실제로는 절반의 순회만으로 충분한 경우가 많습니다.
이 기법의 핵심 특징은 첫째, 공간 복잡도 O(1)로 매우 효율적이고, 둘째, 리스트의 전체 길이를 몰라도 작동하며, 셋째, 사이클이 있는 리스트도 안전하게 처리할 수 있다는 점입니다. 이러한 특징들이 실무에서 메모리가 제한된 환경이나, 실시간 데이터 스트림 처리에서 매우 중요합니다.
코드 예제
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def two_pointer_template(head):
# 기본 템플릿: 느린 포인터와 빠른 포인터 초기화
slow = head
fast = head
# 빠른 포인터가 끝에 도달할 때까지 반복
while fast and fast.next:
slow = slow.next # 한 칸 이동
fast = fast.next.next # 두 칸 이동
# 여기서 slow와 fast의 관계를 활용한 로직 수행
# 예: 사이클 체크 if slow == fast: return True
return slow # 보통 slow가 답이 되는 경우가 많음
설명
이것이 하는 일: 투 포인터 기법은 연결 리스트에서 두 개의 포인터를 동시에 움직이면서, 이들의 상대적 위치나 만나는 시점을 이용해 문제를 해결하는 전략입니다. 코드를 단계별로 살펴보면, 첫 번째로 slow와 fast 두 포인터를 모두 리스트의 head에서 시작합니다.
이것이 기본 출발점입니다. 왜 이렇게 하는지 이해하려면, 두 포인터의 속도 차이가 만들어내는 수학적 관계를 생각해야 합니다.
fast가 slow보다 두 배 빠르게 움직이면, slow가 중간에 도달했을 때 fast는 끝에 도달하게 됩니다. 그 다음으로, while 루프가 실행되면서 매 반복마다 slow는 한 칸, fast는 두 칸씩 이동합니다.
fast and fast.next를 체크하는 이유는 fast.next.next에 접근하기 전에 null 포인터 에러를 방지하기 위함입니다. 내부에서는 두 포인터의 현재 위치를 비교하거나, slow의 위치를 결과로 활용하는 등의 로직이 들어갑니다.
마지막으로, 루프가 종료되면 slow는 정확히 원하는 위치에 도달해 있습니다. 예를 들어 중간 노드를 찾는 경우라면 slow가 중간에, 사이클을 찾는 경우라면 slow와 fast가 만난 지점에 있게 됩니다.
이렇게 한 번의 순회만으로 목표를 달성하는 것이 이 기법의 핵심입니다. 여러분이 이 코드를 사용하면 리스트의 전체 길이를 모르거나 사이클이 있을 수 있는 상황에서도 안전하게 원하는 노드를 찾을 수 있습니다.
또한 O(1)의 추가 공간만 사용하므로 메모리 효율적이고, 리스트를 한 번만 순회하므로 시간도 절약됩니다. 실무에서 대용량 데이터나 스트리밍 데이터를 다룰 때 특히 유용합니다.
실전 팁
💡 항상 fast.next를 체크하세요. fast.next.next에 접근하기 전에 null 체크를 하지 않으면 런타임 에러가 발생합니다. while fast and fast.next 조건이 표준 패턴입니다.
💡 엣지 케이스를 잊지 마세요. 빈 리스트(head is None)나 노드가 하나뿐인 경우를 항상 먼저 처리하세요. 이런 경우에는 투 포인터가 제대로 작동하지 않을 수 있습니다.
💡 포인터의 속도는 문제에 따라 조정할 수 있습니다. 항상 2배 속도일 필요는 없으며, 3배나 N칸 간격을 둔 포인터도 특정 문제에서 유용합니다.
💡 디버깅할 때는 각 반복마다 slow와 fast의 값을 출력해보세요. 포인터의 움직임을 시각적으로 추적하면 로직을 이해하기 훨씬 쉽습니다.
💡 이 패턴을 마스터하면 LeetCode의 연결 리스트 문제 중 70% 이상을 해결할 수 있습니다. 실무 면접에서도 자주 나오는 필수 패턴입니다.
2. 연결 리스트 중간 노드 찾기
시작하며
여러분이 연결 리스트를 절반으로 나누는 기능을 구현해야 한다고 상상해보세요. 리스트의 총 길이를 모르는 상황에서, 어떻게 정확히 중간 지점을 찾을 수 있을까요?
처음부터 끝까지 세어서 길이를 구한 다음, 다시 절반만큼 이동하는 방법은 너무 비효율적입니다. 이런 문제는 실제로 병합 정렬을 연결 리스트에 적용할 때나, 리스트를 여러 파티션으로 나누는 분산 처리에서 자주 발생합니다.
두 번 순회하는 것은 시간 낭비이고, 전체 리스트를 배열로 변환하는 것은 메모리 낭비입니다. 바로 이럴 때 투 포인터 기법을 사용하면, 단 한 번의 순회로 정확히 중간 노드를 찾을 수 있습니다.
fast 포인터가 끝에 도달하는 순간, slow 포인터는 자동으로 중간에 위치하게 됩니다.
개요
간단히 말해서, slow와 fast 두 포인터를 동시에 움직이되 fast가 두 배 빠르게 이동하면, fast가 끝에 도달했을 때 slow는 정확히 중간에 위치하게 됩니다. 이 방법이 필요한 이유는 연결 리스트는 배열과 달리 인덱스 접근이 불가능하기 때문입니다.
리스트의 길이가 n이라면, slow는 n/2번 이동하고 fast는 n번 이동합니다. 이 수학적 관계가 한 번의 순회로 중간을 찾게 해줍니다.
예를 들어, 병합 정렬에서 리스트를 재귀적으로 분할할 때나, 리스트의 앞뒤 절반을 다르게 처리해야 하는 경우에 매우 유용합니다. 기존에는 첫 번째 순회로 전체 길이 n을 계산하고, 두 번째 순회로 n/2 지점까지 이동했다면, 이제는 두 포인터를 동시에 움직여서 한 번에 해결할 수 있습니다.
시간 복잡도는 여전히 O(n)이지만, 실제로는 한 번만 순회하므로 약 2배 빠릅니다. 이 방법의 핵심 특징은 첫째, 리스트 길이를 몰라도 작동하고, 둘째, 추가 메모리가 거의 필요 없으며(O(1)), 셋째, 홀수/짝수 길이 리스트 모두에서 정확히 작동한다는 점입니다.
홀수 길이면 정확히 중간 노드를, 짝수 길이면 중간 두 노드 중 두 번째를 반환합니다. 이러한 일관성이 실무에서 알고리즘을 안정적으로 만들어줍니다.
코드 예제
def find_middle_node(head):
# 엣지 케이스: 빈 리스트나 노드가 하나만 있는 경우
if not head or not head.next:
return head
slow = head
fast = head
# fast가 끝에 도달하면 slow는 중간에 위치
while fast and fast.next:
slow = slow.next # 한 칸 이동
fast = fast.next.next # 두 칸 이동
# slow가 중간 노드를 가리킴
# 짝수 길이: 중간 두 노드 중 두 번째
# 홀수 길이: 정확히 중간 노드
return slow
설명
이것이 하는 일: 이 알고리즘은 두 포인터의 속도 차이를 이용해 리스트를 한 번만 순회하면서 중간 노드를 정확히 찾아냅니다. 코드를 단계별로 살펴보면, 첫 번째로 엣지 케이스를 처리합니다.
빈 리스트나 노드가 하나만 있는 경우는 그대로 head를 반환합니다. 이 체크를 하지 않으면 다음 단계에서 null 포인터 에러가 발생할 수 있습니다.
실무에서는 이런 경계 조건 처리가 버그를 예방하는 핵심입니다. 그 다음으로, slow와 fast를 모두 head에서 시작하여 while 루프를 실행합니다.
매 반복마다 slow는 한 노드씩, fast는 두 노드씩 전진합니다. 예를 들어 5개 노드가 있다면: 1단계에서 slow는 노드1→노드2, fast는 노드1→노드3.
2단계에서 slow는 노드2→노드3, fast는 노드3→노드5. 3단계에서 fast.next가 None이므로 루프 종료.
이때 slow는 노드3(중간)에 위치합니다. 마지막으로, 루프가 종료되는 조건을 정확히 이해하는 것이 중요합니다.
fast.next가 None이 되면 fast는 마지막 노드에 있고, 이때 slow는 정확히 중간에 있습니다. 짝수 길이 리스트(예: 4개 노드)에서는 slow가 3번째 노드에 위치하는데, 이는 중간 두 노드 중 두 번째입니다.
홀수 길이에서는 정확히 가운데 노드를 가리킵니다. 여러분이 이 코드를 사용하면 병합 정렬, 리스트 역순 배치, 회문 검사 등 중간 지점이 필요한 모든 알고리즘에서 효율적으로 작동합니다.
실무에서 대용량 연결 리스트를 처리할 때 두 번 순회하는 것과 비교해 거의 2배의 성능 향상을 얻을 수 있고, 코드도 더 간결하고 이해하기 쉬워집니다.
실전 팁
💡 중간의 "첫 번째" 노드를 원한다면 fast를 head.next에서 시작하세요. 이렇게 하면 짝수 길이에서 중간 두 노드 중 첫 번째를 얻습니다.
💡 병합 정렬 구현 시 중간 노드의 이전 노드도 필요한 경우가 많습니다. 이때는 slow의 이전 노드를 추적하는 prev 포인터를 추가하세요.
💡 리스트를 두 부분으로 나누려면 중간 노드를 찾은 후 middle.next를 저장하고 middle.next = None으로 끊어주세요. 이렇게 하면 두 개의 독립적인 리스트가 됩니다.
💡 성능 테스트를 해보면 두 번 순회하는 방법보다 약 40-50% 빠릅니다. 캐시 지역성이 좋아지기 때문에 이론적인 2배보다는 적지만 여전히 큰 차이입니다.
💡 이 패턴은 면접에서 "follow-up" 질문으로 자주 나옵니다. "공간 복잡도를 O(1)로 유지하면서 한 번만 순회할 수 있나요?"라는 질문에 이것이 답입니다.
3. 사이클 탐지하기
시작하며
여러분이 소셜 네트워크의 친구 추천 시스템을 디버깅하는데, 무한 루프에 빠지는 버그를 발견했다고 가상해보세요. 사용자 A가 B를 참조하고, B가 C를, C가 다시 A를 참조하는 순환 구조가 생긴 것입니다.
이런 사이클을 탐지하지 못하면 프로그램이 멈추거나 스택 오버플로우가 발생합니다. 이런 문제는 그래프 구조, 메모리 누수 탐지, 분산 시스템의 데드락 감지 등에서 실제로 자주 발생합니다.
전통적인 방법은 방문한 노드를 HashSet에 저장해서 중복을 체크하는 것인데, 이는 O(n)의 추가 메모리가 필요합니다. 수백만 개의 노드가 있다면 메모리 부담이 큽니다.
바로 이럴 때 필요한 것이 플로이드의 사이클 탐지 알고리즘(Floyd's Cycle Detection)입니다. "토끼와 거북이" 알고리즘이라고도 불리며, 추가 메모리 없이 사이클을 확실하게 탐지할 수 있습니다.
두 포인터가 만나면 사이클이 있다는 수학적으로 증명된 방법입니다.
개요
간단히 말해서, 사이클 탐지는 slow와 fast 포인터를 동시에 움직이다가 두 포인터가 만나면 사이클이 존재한다고 판단하는 알고리즘입니다. 왜 이것이 작동하는지 직관적으로 이해해봅시다.
육상 트랙을 생각해보세요. 빠른 주자와 느린 주자가 원형 트랙을 달리면, 빠른 주자는 언젠가 느린 주자를 한 바퀴 돌아서 따라잡게 됩니다.
연결 리스트에서도 마찬가지입니다. 사이클이 있다면 fast가 slow를 언젠가 따라잡고, 사이클이 없다면 fast가 끝(null)에 도달합니다.
이것이 핵심 원리입니다. 기존에는 visited = set()을 만들어 각 노드를 체크했다면, 이제는 포인터 두 개만으로 O(1) 공간에서 해결할 수 있습니다.
시간 복잡도는 여전히 O(n)이지만, 사이클이 있는 경우 실제로는 사이클을 한 바퀴 도는 시간만큼만 추가됩니다. 이 방법의 핵심 특징은 첫째, 공간 복잡도 O(1)로 매우 메모리 효율적이고, 둘째, 수학적으로 증명된 정확성을 가지며, 셋째, 사이클의 존재 여부를 확실하게 판단할 수 있다는 점입니다.
로버트 플로이드가 1960년대에 고안한 이 알고리즘은 60년이 지난 지금도 최적의 솔루션으로 인정받고 있습니다.
코드 예제
def has_cycle(head):
# 엣지 케이스: 빈 리스트나 노드가 하나만 있으면 사이클 없음
if not head or not head.next:
return False
slow = head
fast = head
# fast가 끝에 도달하면 사이클 없음, 만나면 사이클 있음
while fast and fast.next:
slow = slow.next # 거북이: 한 칸
fast = fast.next.next # 토끼: 두 칸
# 두 포인터가 만나면 사이클 존재
if slow == fast:
return True
# fast가 끝(None)에 도달 = 사이클 없음
return False
설명
이것이 하는 일: 플로이드의 사이클 탐지 알고리즘은 두 포인터의 속도 차이를 이용해 연결 리스트에 순환 구조가 있는지 확실하게 판별합니다. 코드를 단계별로 살펴보면, 첫 번째로 엣지 케이스를 확인합니다.
노드가 없거나 하나만 있으면 사이클이 불가능하므로 즉시 False를 반환합니다. 이 체크가 없으면 다음 단계에서 fast.next.next 접근 시 에러가 발생할 수 있습니다.
그 다음으로, while 루프에서 매 반복마다 slow는 한 칸, fast는 두 칸씩 이동합니다. 여기서 중요한 것은 if slow == fast 체크인데, 이것이 사이클 탐지의 핵심입니다.
사이클이 있다면 수학적으로 fast와 slow는 반드시 만나게 됩니다. 왜냐하면 사이클 안에서 fast가 slow보다 한 칸씩 가까워지기 때문입니다.
거리가 d라면, 매 반복마다 (d-1), (d-2), ..., 1, 0이 되어 결국 만납니다. 마지막으로, 루프가 정상 종료되면(fast가 None에 도달) 사이클이 없다는 뜻이므로 False를 반환합니다.
반면 루프 중간에 slow == fast가 되면 즉시 True를 반환합니다. 이 두 가지 경우가 모든 가능성을 커버합니다.
여러분이 이 코드를 사용하면 대용량 그래프 데이터에서도 메모리 걱정 없이 사이클을 탐지할 수 있습니다. 예를 들어 천만 개의 노드가 있는 경우, HashSet 방식은 수백 MB의 메모리를 쓰지만 이 방법은 단 두 개의 포인터 변수만 사용합니다.
실무에서 메모리 제약이 있는 임베디드 시스템이나 모바일 환경에서 특히 유용하며, GC(가비지 컬렉션) 압력도 줄어듭니다.
실전 팁
💡 사이클의 길이를 구하고 싶다면 만난 지점에서 slow는 고정하고 fast만 계속 이동시켜 다시 만날 때까지 카운트하세요. 그 횟수가 사이클 길이입니다.
💡 실무에서는 타임아웃을 추가로 설정하세요. 예를 들어 max_iterations를 설정해서 무한 루프를 방지하는 안전장치를 더하면 더욱 안정적입니다.
💡 디버깅할 때 무한 루프에 빠졌다고 의심되면 이 알고리즘을 먼저 실행해보세요. 사이클 여부를 빠르게 확인할 수 있습니다.
💡 이 알고리즘은 그래프 이론의 DFS와 함께 사용하면 더 강력합니다. 방향 그래프에서 백엣지를 찾는 것과 결합하면 모든 종류의 사이클을 탐지할 수 있습니다.
💡 면접에서 "공간 복잡도를 최적화할 수 있나요?"라는 질문이 나오면 이 알고리즘을 설명하세요. 이것이 공간 복잡도 O(1)의 최적해입니다.
4. 사이클 시작점 찾기
시작하며
여러분이 사이클이 있는 연결 리스트를 발견했습니다. 하지만 단순히 사이클이 있다는 것만 아는 것으로는 충분하지 않습니다.
메모리 누수를 수정하거나, 잘못된 참조를 고치려면 정확히 어느 노드에서 사이클이 시작되는지 알아야 합니다. 사이클의 첫 노드를 찾는 것이 문제 해결의 핵심입니다.
이 문제는 실무에서 순환 참조로 인한 메모리 누수 디버깅, 분산 시스템에서 데드락의 시작점 찾기, 그래프 알고리즘에서 백엣지의 목적지 찾기 등에서 자주 마주칩니다. 단순히 모든 노드를 HashSet에 넣어서 중복을 찾는 방법은 O(n) 메모리가 필요합니다.
바로 이럴 때 플로이드 알고리즘의 확장 버전을 사용합니다. 놀랍게도, 두 포인터가 만난 후 한 포인터를 head로 되돌리고 둘 다 같은 속도로 움직이면, 다시 만나는 지점이 바로 사이클의 시작점입니다.
이것은 수학적으로 증명된 아름다운 성질입니다.
개요
간단히 말해서, 사이클 탐지 후 한 포인터를 head로 리셋하고 두 포인터를 같은 속도(한 칸씩)로 움직이면, 이들이 만나는 지점이 사이클의 시작 노드입니다. 이 방법이 작동하는 수학적 원리를 간단히 설명하겠습니다.
head에서 사이클 시작까지 거리를 a, 사이클 시작에서 만난 지점까지를 b, 만난 지점에서 사이클 시작까지를 c라고 하면, slow가 이동한 거리는 a+b이고 fast는 a+b+c+b(한 바퀴 더)입니다. fast가 두 배 빠르므로 2(a+b) = a+2b+c, 정리하면 a = c입니다.
따라서 head에서 a만큼, 만난 지점에서 c만큼 이동하면 같은 지점(사이클 시작)에서 만납니다. 기존에는 각 노드를 HashSet에 넣으면서 처음 중복되는 노드를 찾았다면, 이제는 포인터 조작만으로 O(1) 공간에서 해결할 수 있습니다.
이것은 알고리즘의 우아함을 보여주는 완벽한 예입니다. 이 방법의 핵심 특징은 첫째, 여전히 O(1) 공간 복잡도를 유지하고, 둘째, 수학적으로 정확하게 사이클 시작점을 찾으며, 셋째, 사이클 탐지와 시작점 찾기를 하나의 알고리즘으로 통합할 수 있다는 점입니다.
이 두 단계를 분리하지 않고 하나의 함수로 작성하면 매우 효율적입니다.
코드 예제
def detect_cycle_start(head):
if not head or not head.next:
return None
# 1단계: 사이클 탐지 (플로이드 알고리즘)
slow = fast = head
has_cycle = False
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
has_cycle = True
break
# 사이클이 없으면 None 반환
if not has_cycle:
return None
# 2단계: 사이클 시작점 찾기
# slow를 head로 리셋, fast는 만난 지점에 유지
slow = head
while slow != fast:
slow = slow.next # 한 칸씩
fast = fast.next # 한 칸씩 (더 이상 두 칸 아님!)
# 만나는 지점이 사이클 시작 노드
return slow
설명
이것이 하는 일: 이 알고리즘은 플로이드 사이클 탐지를 확장하여 사이클의 정확한 시작 노드를 추가 메모리 없이 찾아냅니다. 코드를 단계별로 살펴보면, 첫 번째 단계는 일반적인 사이클 탐지입니다.
slow와 fast를 이동시키면서 만나는지 확인합니다. 만나면 has_cycle을 True로 설정하고 break로 루프를 빠져나옵니다.
이때 중요한 것은 slow와 fast가 만난 정확한 위치를 유지하는 것입니다. 이 위치가 다음 단계의 시작점이 되기 때문입니다.
그 다음으로, 사이클이 없으면 None을 반환하고 종료합니다. 사이클이 있다면 2단계로 진입하는데, 여기서 핵심은 slow를 head로 리셋하고 fast는 만난 지점에 그대로 두는 것입니다.
이제 두 포인터를 같은 속도(한 칸씩!)로 움직입니다. 수학적으로 head에서 사이클 시작까지의 거리와 만난 지점에서 사이클 시작까지의 거리가 같기 때문에, 이들은 정확히 사이클 시작점에서 만나게 됩니다.
마지막으로, while slow != fast 루프가 종료되면 slow(또는 fast, 같은 위치니까)가 사이클의 시작 노드를 가리킵니다. 이것을 반환하면 됩니다.
이 알고리즘의 아름다움은 복잡한 수학을 코드로 구현하면 이렇게 간결해진다는 점입니다. 여러분이 이 코드를 사용하면 메모리 누수가 발생한 정확한 지점을 찾아서 수정할 수 있습니다.
실무에서 순환 참조 문제를 디버깅할 때, 어떤 객체가 잘못 참조되고 있는지 정확히 식별할 수 있어서 매우 유용합니다. 또한 그래프 알고리즘에서 백엣지의 목적지를 찾거나, 위상 정렬이 불가능한 이유를 파악하는 데도 활용됩니다.
실전 팁
💡 2단계에서 fast도 한 칸씩 이동하는 것을 잊지 마세요. 많은 사람들이 실수로 fast.next.next를 써서 틀립니다. 두 번째 단계에서는 같은 속도입니다!
💡 수학적 증명을 이해하면 면접에서 큰 플러스입니다. a = c 관계를 화이트보드에 설명할 수 있으면 깊은 이해를 보여줄 수 있습니다.
💡 사이클 시작점을 찾으면 거기서 사이클을 끊을 수 있습니다. 사이클 직전 노드를 찾아서 .next = None으로 설정하면 정상 리스트가 됩니다.
💡 이 알고리즘은 여러 사이클이 있을 때는 작동하지 않습니다. 연결 리스트는 노드당 next가 하나뿐이므로 최대 하나의 사이클만 가능하지만, 일반 그래프에서는 주의하세요.
💡 LeetCode 142번 "Linked List Cycle II" 문제가 이것입니다. 이 패턴을 익히면 비슷한 문제들을 쉽게 해결할 수 있습니다.
5. 끝에서 N번째 노드 찾기
시작하며
여러분이 로그 파일의 마지막 10줄을 출력하는 기능을 구현해야 한다고 상상해보세요. 로그가 연결 리스트 형태로 스트리밍되고 있고, 전체 길이를 모릅니다.
어떻게 하시겠습니까? 전체를 버퍼에 담았다가 끝에서 10개를 세는 것은 메모리 낭비고, 두 번 읽는 것은 비효율적입니다.
이런 문제는 실제로 스트리밍 데이터 처리, 로그 모니터링, 실시간 분석에서 자주 발생합니다. 배열이라면 array[length - n]으로 간단하지만, 연결 리스트는 역방향 인덱싱이 불가능합니다.
전체를 배열로 변환하는 것은 공간 낭비입니다. 바로 이럴 때 두 포인터를 N칸 간격으로 유지하면서 이동시키는 기법을 사용합니다.
앞 포인터가 끝에 도달했을 때, 뒤 포인터는 자동으로 끝에서 N번째 위치에 있게 됩니다. 한 번의 순회로 해결되는 우아한 방법입니다.
개요
간단히 말해서, 두 포인터를 N칸 간격으로 유지하면서 함께 이동시키면, 앞 포인터가 끝에 도달했을 때 뒤 포인터는 자동으로 끝에서 N번째 노드에 위치합니다. 이 방법이 필요한 이유는 연결 리스트에서는 역방향 접근이 불가능하기 때문입니다.
N칸 간격을 유지한다는 것은 수학적으로 첫 번째 포인터가 위치 i에 있으면 두 번째는 i-N에 있다는 뜻입니다. 첫 번째가 끝(length)에 도달하면 두 번째는 length-N에 있게 되는 원리입니다.
예를 들어, GitHub의 recent commits를 보여주거나, 음악 재생 목록에서 최근 N곡을 추천하는 등의 기능에 유용합니다. 기존에는 첫 번째 순회로 전체 길이를 세고, 두 번째 순회로 (length-N)번째 노드까지 이동했다면, 이제는 포인터 간격만 유지하면서 한 번에 해결할 수 있습니다.
시간 복잡도는 O(n)으로 동일하지만 실제로는 절반의 시간만 걸립니다. 이 방법의 핵심 특징은 첫째, 리스트의 전체 길이를 몰라도 작동하고, 둘째, 한 번의 순회만 필요하며, 셋째, 메모리 사용이 O(1)로 매우 효율적이라는 점입니다.
스트리밍 환경에서 특히 강력한데, 데이터가 실시간으로 들어오는 상황에서도 바로 적용할 수 있기 때문입니다.
코드 예제
def find_nth_from_end(head, n):
# 엣지 케이스: 빈 리스트
if not head:
return None
# 두 포인터를 모두 head에서 시작
first = head
second = head
# first를 N칸 앞으로 이동
for i in range(n):
if not first:
# N이 리스트 길이보다 큰 경우
return None
first = first.next
# 이제 first와 second를 함께 이동
# first가 끝에 도달하면 second는 끝에서 N번째
while first:
first = first.next
second = second.next
return second
설명
이것이 하는 일: 이 알고리즘은 두 포인터 사이의 일정한 간격을 유지하면서 리스트를 순회하여, 한 번의 패스로 끝에서 N번째 노드를 정확히 찾아냅니다. 코드를 단계별로 살펴보면, 첫 번째로 빈 리스트 체크를 합니다.
그 다음 중요한 단계는 first 포인터를 N칸 앞으로 먼저 이동시키는 것입니다. for 루프에서 N번 반복하면서 first = first.next를 수행합니다.
이때 first가 None이 되면 N이 리스트 길이보다 크다는 뜻이므로 None을 반환합니다. 예를 들어 노드가 5개인데 N=7이면 불가능하므로 에러 처리가 필요합니다.
그 다음으로, first와 second 사이에 정확히 N칸 간격이 생긴 상태에서 while 루프를 시작합니다. 매 반복마다 두 포인터를 모두 한 칸씩 이동시킵니다.
중요한 것은 이 간격이 계속 유지된다는 점입니다. first가 1번째에서 2번째로 가면 second도 -N번째에서 -N+1번째로 이동하므로 상대적 거리는 항상 N입니다.
마지막으로, while first 조건이 거짓이 되면(first가 None) 루프가 종료되는데, 이때 first는 리스트의 끝을 넘어선 상태이고 second는 정확히 끝에서 N번째 노드를 가리킵니다. 예를 들어 길이가 10이고 N=3이면, first가 11번째(None)에 도달했을 때 second는 8번째(끝에서 3번째)에 있습니다.
여러분이 이 코드를 사용하면 대용량 스트리밍 데이터에서도 메모리 걱정 없이 최근 N개 항목을 추적할 수 있습니다. 실무에서 로그 모니터링 시스템, 최근 활동 추적, 슬라이딩 윈도우 알고리즘 등에 직접 활용됩니다.
특히 전체 데이터를 저장할 수 없는 제약이 있을 때 이 패턴이 유일한 해결책이 되기도 합니다.
실전 팁
💡 N번째를 삭제하려면 second의 이전 노드가 필요합니다. 이때는 second를 한 칸 늦게 시작하거나, prev 포인터를 추가로 유지하세요.
💡 N이 0이거나 음수인 경우를 처리하세요. 함수 시작 부분에 if n <= 0: return None을 추가하는 것이 좋습니다.
💡 LeetCode 19번 "Remove Nth Node From End" 문제는 이 패턴의 변형입니다. 노드를 찾는 대신 삭제하면 됩니다.
💡 이 패턴은 "슬라이딩 윈도우"의 연결 리스트 버전으로 볼 수 있습니다. 배열에서의 two pointers와 같은 개념이 연결 리스트에서는 이렇게 구현됩니다.
💡 실무에서는 N이 매우 클 수 있으므로, N > 리스트 길이인 경우의 에러 처리를 명확히 하세요. 로그를 남기거나 예외를 던지는 것이 좋습니다.
6. 두 연결 리스트 교차점 찾기
시작하며
여러분이 버전 관리 시스템을 개발하는데, 두 개의 브랜치가 어느 커밋에서 갈라졌는지 찾아야 한다고 상상해보세요. 각 브랜치는 연결 리스트처럼 커밋을 따라가고, 어느 시점에서 공통 조상을 공유합니다.
이 교차점을 찾는 것이 머지 베이스를 결정하는 핵심입니다. 이런 문제는 실제로 Git 같은 VCS, 파일 시스템의 하드링크, 객체 그래프의 공유 참조 등에서 자주 발생합니다.
간단한 방법은 한 리스트의 모든 노드를 HashSet에 넣고 다른 리스트를 순회하면서 중복을 찾는 것인데, 이는 O(n) 메모리가 필요합니다. 바로 이럴 때 투 포인터를 이용한 우아한 해법이 있습니다.
두 리스트의 길이 차이를 처리하고, 양쪽에서 동시에 순회하면서 만나는 지점을 찾습니다. 핵심은 두 포인터가 각자의 리스트 끝에 도달하면 상대방 리스트의 head로 이동하는 것입니다.
이렇게 하면 자동으로 길이 차이가 상쇄됩니다.
개요
간단히 말해서, 두 포인터가 각자의 리스트를 순회하다가 끝에 도달하면 상대방의 리스트로 넘어가도록 하면, 길이가 달라도 교차점에서 정확히 만나게 됩니다. 이 방법이 작동하는 원리를 수학적으로 보겠습니다.
리스트 A의 길이가 a, 리스트 B의 길이가 b라고 하고, 교차점까지 A는 m, B는 n이라고 하면, 포인터가 A→B 경로를 따르면 m + (b-공통) + 공통을, B→A 경로를 따르면 n + (a-공통) + 공통을 이동합니다. 수식을 정리하면 두 경로의 길이가 같아져서 교차점에서 만나게 됩니다.
기존에는 한 리스트를 HashSet에 모두 저장(O(n) 공간)했다면, 이제는 포인터 두 개만으로 O(1) 공간에서 해결할 수 있습니다. 시간 복잡도는 O(a+b)로 여전히 선형이지만, 공간을 획기적으로 줄입니다.
이 방법의 핵심 특징은 첫째, 두 리스트의 길이가 달라도 자동으로 처리되고, 둘째, 추가 메모리가 거의 필요 없으며, 셋째, 교차점이 없어도 안전하게 None을 반환한다는 점입니다. 코드가 간결하면서도 모든 경우를 커버하는 것이 이 알고리즘의 아름다움입니다.
코드 예제
def get_intersection_node(headA, headB):
# 엣지 케이스: 둘 중 하나라도 빈 리스트면 교차 불가
if not headA or not headB:
return None
# 두 포인터 초기화
pointerA = headA
pointerB = headB
# 교차점에서 만나거나, 둘 다 None이 될 때까지 반복
while pointerA != pointerB:
# A 끝에 도달하면 B의 head로, 아니면 다음 노드로
pointerA = headB if not pointerA else pointerA.next
# B 끝에 도달하면 A의 head로, 아니면 다음 노드로
pointerB = headA if not pointerB else pointerB.next
# 교차점을 반환 (없으면 None, 있으면 교차 노드)
return pointerA
설명
이것이 하는 일: 이 알고리즘은 두 포인터를 교차 경로로 이동시켜 길이가 다른 두 리스트에서도 교차점을 정확히 찾아냅니다. 코드를 단계별로 살펴보면, 첫 번째로 엣지 케이스를 처리합니다.
둘 중 하나라도 비어있으면 교차할 수 없으므로 None을 반환합니다. 그 다음 pointerA와 pointerB를 각각의 head에서 시작합니다.
그 다음으로, while pointerA != pointerB 루프가 핵심입니다. 각 반복에서 포인터가 끝(None)에 도달했는지 확인합니다.
pointerA가 None이면 headB로 전환하고, 아니면 pointerA.next로 이동합니다. pointerB도 마찬가지입니다.
이 "스위칭" 메커니즘이 마법을 만들어냅니다. 예를 들어 설명하겠습니다.
A가 [1,2,3,4,5,6] (6에서 교차), B가 [9,6] (6에서 교차)라고 하면: - pointerA: 1→2→3→4→5→6→(끝)→9→6 (총 8단계) - pointerB: 9→6→(끝)→1→2→3→4→5→6 (총 8단계) 양쪽 다 8단계 후에 교차점 6에서 만납니다! 마지막으로, 루프가 종료되는 경우는 두 가지입니다.
첫째, 교차점에서 pointerA == pointerB가 되는 경우 - 이때 그 노드를 반환합니다. 둘째, 교차점이 없어서 둘 다 None이 되는 경우 - 이때도 pointerA == pointerB (둘 다 None)이므로 루프가 종료되고 None을 반환합니다.
두 경우 모두 올바르게 처리됩니다. 여러분이 이 코드를 사용하면 복잡한 객체 그래프에서 공유 참조를 찾거나, 파일 시스템에서 하드링크를 추적하거나, Git의 merge-base 같은 기능을 구현할 수 있습니다.
메모리를 거의 쓰지 않으면서도 정확하게 작동하므로, 대규모 시스템에서 특히 유용합니다.
실전 팁
💡 교차점 이후의 노드들은 완전히 동일한 객체여야 합니다. 값만 같은 게 아니라 메모리 주소가 같아야 합니다. 이를 테스트하려면 id() 함수나 is 연산자를 사용하세요.
💡 무한 루프를 걱정할 수 있지만, 수학적으로 최대 a+b 반복 후 반드시 종료됩니다. 하지만 안전을 위해 max_iterations를 추가할 수도 있습니다.
💡 이 알고리즘의 변형으로, 먼저 두 리스트의 길이를 구해서 차이만큼 긴 리스트를 먼저 이동시키는 방법도 있습니다. 하지만 위 방법이 더 간결하고 우아합니다.
💡 LeetCode 160번 "Intersection of Two Linked Lists"가 이 문제입니다. 다양한 엣지 케이스(교차 없음, 완전히 같은 리스트 등)를 테스트해보세요.
💡 실무에서는 순환 참조가 있을 수 있으니 주의하세요. 이 알고리즘은 사이클이 없다고 가정합니다. 사이클이 있으면 먼저 사이클 탐지를 수행하세요.
7. 연결 리스트 회문 검사
시작하며
여러분이 문자열을 연결 리스트로 저장하는 시스템을 만들고 있는데, 이것이 회문(앞뒤가 같은 문자열)인지 확인해야 한다고 상상해보세요. 배열이라면 양 끝에서 비교하면 되지만, 연결 리스트는 뒤에서부터 접근할 수 없습니다.
전체를 배열로 복사하는 것은 메모리 낭비고, 재귀로 스택을 쌓는 것도 공간이 많이 듭니다. 이런 문제는 실무에서 데이터 검증, 암호화 알고리즘, 문자열 처리 라이브러리 등에서 나타납니다.
회문 검사는 간단해 보이지만, 연결 리스트에서는 까다로운 문제입니다. 효율적으로 해결하려면 창의적인 접근이 필요합니다.
바로 이럴 때 투 포인터로 중간을 찾고, 후반부를 뒤집은 다음, 앞부분과 비교하는 방법을 사용합니다. O(1) 추가 공간으로 해결할 수 있는 우아한 방법입니다.
개요
간단히 말해서, 중간 노드를 찾아서 후반부 리스트를 역순으로 뒤집은 다음, 앞부분과 뒤집힌 뒷부분을 하나씩 비교하면 회문인지 확인할 수 있습니다. 이 방법이 필요한 이유는 연결 리스트에서 역방향 접근이 불가능하기 때문입니다.
하지만 리스트 자체를 물리적으로 뒤집으면 앞에서부터 비교할 수 있게 됩니다. 예를 들어, [1,2,3,2,1]이라는 리스트에서 중간(3) 이후를 뒤집으면 [1,2,3] [1,2]가 되고, 이 둘을 비교하면 회문임을 알 수 있습니다.
기존에는 리스트를 배열로 변환(O(n) 공간) 하거나 재귀 호출로 스택을 사용(O(n) 공간)했다면, 이제는 포인터 조작만으로 O(1) 공간에서 해결할 수 있습니다. 시간 복잡도는 O(n)이지만 공간은 획기적으로 줄어듭니다.
이 방법의 핵심 특징은 첫째, 투 포인터로 중간을 찾고(배운 내용 활용!), 둘째, 후반부를 in-place로 뒤집으며, 셋째, 비교 후 원래대로 복구할 수도 있다는 점입니다. 이 세 단계를 조합하면 매우 효율적인 솔루션이 됩니다.
코드 예제
def is_palindrome(head):
if not head or not head.next:
return True
# 1단계: 중간 노드 찾기 (투 포인터)
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 2단계: 후반부 리스트 뒤집기
prev = None
while slow:
next_node = slow.next
slow.next = prev
prev = slow
slow = next_node
# 3단계: 앞부분과 뒤집힌 뒷부분 비교
left = head
right = prev # 뒤집힌 후반부의 head
while right: # 짧은 쪽 기준
if left.val != right.val:
return False
left = left.next
right = right.next
return True
설명
이것이 하는 일: 이 알고리즘은 투 포인터, 리스트 뒤집기, 비교라는 세 가지 테크닉을 조합하여 추가 메모리 없이 회문을 검사합니다. 코드를 단계별로 살펴보면, 첫 번째 단계는 우리가 배운 투 포인터 기법으로 중간 노드를 찾는 것입니다.
slow와 fast를 이용해 slow가 중간에 도달하게 합니다. 홀수 길이면 정확히 중간, 짝수 길이면 중간 두 개 중 두 번째를 가리킵니다.
이것이 후반부의 시작점이 됩니다. 그 다음으로, 후반부 리스트를 in-place로 뒤집습니다.
이것은 연결 리스트 뒤집기의 표준 알고리즘입니다. prev를 None으로 초기화하고, 각 노드의 next를 이전 노드로 바꿔가면서 진행합니다.
루프가 끝나면 prev가 뒤집힌 리스트의 새로운 head가 됩니다. 예를 들어 [1,2,3,2,1]에서 [3,2,1] 부분이 [1,2,3]으로 뒤집힙니다.
마지막으로, 앞부분(left)과 뒤집힌 뒷부분(right)을 동시에 순회하면서 값을 비교합니다. while right 조건을 쓰는 이유는 홀수 길이일 때 후반부가 더 짧기 때문입니다.
하나라도 다르면 즉시 False를 반환하고, 끝까지 같으면 True를 반환합니다. 이 비교 과정은 O(n/2) = O(n)입니다.
여러분이 이 코드를 사용하면 대용량 문자열 데이터를 연결 리스트로 처리할 때 메모리 효율적으로 회문을 검사할 수 있습니다. 실무에서 데이터 검증 파이프라인, 문자열 처리 라이브러리, 알고리즘 면접 등에서 유용합니다.
특히 이 문제는 여러 개념(투 포인터, 리스트 뒤집기, 비교)을 통합하는 능력을 보여주는 좋은 예제입니다.
실전 팁
💡 원본 리스트를 보존해야 한다면 3단계 후에 후반부를 다시 뒤집어서 복구하세요. 같은 뒤집기 로직을 한 번 더 수행하면 됩니다.
💡 홀수 길이 리스트에서 중간 노드는 비교하지 않아도 됩니다. 어차피 자기 자신과 같으므로 회문 판단에 영향을 주지 않습니다.
💡 LeetCode 234번 "Palindrome Linked List"가 이 문제입니다. follow-up으로 O(n) 시간, O(1) 공간을 요구하는데 바로 이 방법입니다.
💡 스택을 사용하는 방법(후반부를 스택에 넣고 pop하면서 비교)도 직관적이지만 O(n) 공간을 씁니다. 면접에서 둘 다 설명하고 trade-off를 논의하면 좋습니다.
💡 디버깅할 때는 각 단계 후에 리스트 상태를 출력해보세요. 중간 찾기, 뒤집기, 비교 각 단계가 올바르게 작동하는지 확인할 수 있습니다.
8. 연결 리스트를 두 부분으로 분할하기
시작하며
여러분이 병합 정렬을 연결 리스트에 구현하고 있다고 상상해보세요. 분할 정복 전략의 핵심은 리스트를 두 개의 거의 같은 크기로 나누는 것입니다.
하지만 배열처럼 인덱스로 간단히 자를 수 없습니다. 어떻게 정확히 중간에서 리스트를 물리적으로 분리할 수 있을까요?
이런 문제는 실제로 병합 정렬, 퀵 정렬, 분산 처리에서 데이터 파티셔닝 등에서 자주 발생합니다. 리스트를 복사하지 않고 in-place로 분할하는 것이 메모리 효율성을 위해 중요합니다.
잘못 분할하면 알고리즘 전체가 틀어집니다. 바로 이럴 때 투 포인터로 중간을 찾고, 그 지점에서 리스트를 끊어서 두 개의 독립적인 리스트로 만드는 기법을 사용합니다.
한 번의 순회로 깔끔하게 분할할 수 있습니다.
개요
간단히 말해서, 투 포인터로 중간 노드를 찾은 다음, 중간 직전 노드의 next를 None으로 설정하여 리스트를 물리적으로 두 부분으로 분리합니다. 이 방법이 필요한 이유는 분할 정복 알고리즘에서 각 부분이 독립적으로 처리되어야 하기 때문입니다.
단순히 중간 노드를 찾는 것만으로는 부족하고, 실제로 연결을 끊어야 두 개의 별도 리스트가 됩니다. 예를 들어, 병합 정렬에서 좌우를 재귀 호출할 때 각각 독립적인 head를 가져야 합니다.
기존에는 리스트를 순회하면서 새로운 노드들을 만들어 복사했다면, 이제는 기존 노드들의 연결만 변경해서 O(1) 추가 공간으로 해결할 수 있습니다. 노드 자체는 그대로 두고 포인터만 조작하는 in-place 연산입니다.
이 방법의 핵심 특징은 첫째, 중간 노드를 찾는 투 포인터 기법을 활용하고, 둘째, 이전 노드를 추적하여 연결을 끊으며, 셋째, 원본 노드들을 재사용하므로 메모리 효율적이라는 점입니다. 병합 정렬 같은 알고리즘에서 이 분할 단계가 효율적이어야 전체 알고리즘도 효율적입니다.
코드 예제
def split_list(head):
# 엣지 케이스: 빈 리스트나 노드 하나
if not head or not head.next:
return head, None
# 중간을 찾되, 이전 노드(prev)도 추적
prev = None
slow = head
fast = head
while fast and fast.next:
prev = slow # slow의 이전 위치 기억
slow = slow.next
fast = fast.next.next
# slow가 중간(또는 중간 두 개 중 두 번째)
# prev는 전반부의 마지막 노드
# 리스트를 두 부분으로 분리
if prev:
prev.next = None # 전반부 끝을 None으로
# 첫 번째 부분: head ~ prev
# 두 번째 부분: slow ~ 끝
return head, slow
설명
이것이 하는 일: 이 알고리즘은 투 포인터로 중간을 찾으면서 동시에 이전 노드를 추적하여, 리스트를 정확히 두 부분으로 물리적으로 분리합니다. 코드를 단계별로 살펴보면, 첫 번째로 엣지 케이스를 처리합니다.
노드가 0개거나 1개면 분할할 수 없으므로 (head, None)을 반환합니다. 이것은 재귀 알고리즘의 베이스 케이스가 됩니다.
그 다음으로, while 루프에서 핵심은 prev = slow 라인입니다. slow를 이동시키기 전에 현재 위치를 prev에 저장합니다.
이렇게 하면 루프가 끝났을 때 prev는 전반부의 마지막 노드를 가리키고, slow는 후반부의 첫 노드를 가리킵니다. 예를 들어 [1,2,3,4,5]에서 루프가 끝나면 prev=2, slow=3이 됩니다.
마지막으로, prev.next = None을 수행하여 물리적으로 리스트를 끊습니다. 이제 head에서 시작하는 리스트는 prev에서 끝나고(next가 None), slow에서 시작하는 리스트는 독립적으로 존재합니다.
두 개의 head(head와 slow)를 튜플로 반환하면, 호출자는 이들을 별도로 처리할 수 있습니다. 여러분이 이 코드를 사용하면 병합 정렬을 연결 리스트에 효율적으로 구현할 수 있습니다.
재귀 호출 시 left, right = split_list(head)로 분할하고, 각각을 정렬한 다음 병합하는 전형적인 패턴입니다. 실무에서 대용량 연결 리스트를 정렬하거나, 데이터를 파티셔닝해서 병렬 처리할 때 이 분할 기법이 필수입니다.
메모리 복사 없이 포인터만 조작하므로 매우 효율적입니다.
실전 팁
💡 분할 후에는 원본 head로 전체 리스트에 접근할 수 없습니다. 필요하다면 분할 전에 참조를 저장해두세요.
💡 홀수 길이 리스트에서 전반부가 한 개 적습니다. [1,2,3]은 [1,2]와 [3]으로 분할됩니다. 이것은 병합 정렬에서 문제없지만 정확히 절반이 필요하면 조정하세요.
💡 병합 정렬 전체 구조는: split → recursive_sort(left) → recursive_sort(right) → merge(left, right) 입니다. 이 split 함수가 첫 단계입니다.
💡 prev가 None인 경우는 노드가 하나뿐일 때입니다. 이때 prev.next를 건드리면 에러가 나므로 if prev 체크가 중요합니다.
💡 이 패턴을 마스터하면 연결 리스트로 퀵 정렬, 버킷 정렬 등 다양한 분할 기반 알고리즘을 구현할 수 있습니다. 분할이 효율적이면 전체 알고리즘도 효율적입니다.