Ch.5 연결 리스트

면접실전 — Linked List 핵심 문제 5선

Reverse, Merge Two Lists, Cycle, Remove Nth, LRU 문제를 풀 수 있다각 문제의 최적 접근법과 엣지 케이스를 설명한다

면접관이 좋아하는 연결 리스트 문제 5개

연결 리스트는 면접에서 포인터 조작 능력을 테스트하는 최고의 주제입니다. 5가지 대표 문제를 통해 실전 감각을 키웁니다.

코드를 외우는 게 아니라, 패턴을 익혀야 변형에 대응할 수 있다

각 문제의 핵심 패턴을 정리하고, 면접에서 어떻게 설명할지 연습합니다.

article

핵심 내용

LeetCode 206 Reverse Linked List

def reverseList(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

# 시간 O(n), 공간 O(1)

패턴: 3포인터(prev/curr/nxt) — 연결 리스트 면접의 기본 중 기본

LeetCode 21 Merge Two Sorted Lists

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  # 남은 리스트 연결
    return dummy.next

# 시간 O(n+m), 공간 O(1)

패턴: dummy head + 두 포인터 비교 — Merge Sort의 merge 단계와 동일

LeetCode 141 / 142 Linked List Cycle I & II

# Cycle I: 사이클 존재 여부
def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Cycle II: 사이클 시작점
def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

패턴: Fast & Slow (Floyd's) — 사이클 + 중간 노드 문제의 만능 도구

LeetCode 19 Remove Nth Node From End of List

def removeNthFromEnd(head, n):
    dummy = ListNode(0)
    dummy.next = head
    fast = slow = dummy
    
    # fast를 n+1칸 앞으로
    for _ in range(n + 1):
        fast = fast.next
    
    # 같이 이동 → fast가 끝이면 slow는 삭제 대상 앞
    while fast:
        fast = fast.next
        slow = slow.next
    
    slow.next = slow.next.next  # 삭제
    return dummy.next

# 시간 O(n), 공간 O(1), 한 번의 순회

패턴: 두 포인터 간격 유지 + dummy head — 끝에서 n번째를 한 번 순회로 찾기

LeetCode 146 LRU Cache — 면접 빈출 Top 5

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}       # key → Node
        self.head = DLLNode() # dummy head
        self.tail = DLLNode() # dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def get(self, key):       # O(1)
        if key not in self.cache: return -1
        node = self.cache[key]
        self._remove(node)
        self._add_front(node)
        return node.val
    
    def put(self, key, val):  # O(1)
        if key in self.cache:
            self._remove(self.cache[key])
        node = DLLNode(key, val)
        self.cache[key] = node
        self._add_front(node)
        if len(self.cache) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

패턴: HashMap + Doubly Linked List — 조회 O(1) + 삽입/삭제 O(1)

Linked List 면접 패턴 5가지 1. 3포인터 Reverse: prev/curr/nxt 2. Dummy Head + Merge: 두 리스트 병합 3. Fast & Slow: 사이클, 중간 노드 4. 간격 유지 두 포인터: 끝에서 n번째 5. HashMap + DLL: LRU Cache

두 정렬된 리스트를 병합할 때 dummy head를 사용하는 이유는?

Remove Nth From End에서 fast를 n+1칸 먼저 보내는 이유는?

면접에서 LRU Cache를 OrderedDict로만 구현하면 만점을 받을 수 있다

면접실전 5문제 정복!

edit_note

정리 노트

Linked List 면접 핵심 문제 5선

필수 문제

LC 206: Reverse — 3포인터
LC 21: Merge Two Lists — dummy + 비교
LC 141/142: Cycle — Fast & Slow
LC 19: Remove Nth — 간격 유지 두 포인터
LC 146: LRU Cache — HashMap + DLL

공통 테크닉

dummy head: head 변경 가능 문제의 엣지 케이스 제거
포인터 순서: 연결 끊기 전에 다음 노드 미리 저장

★

5문제를 30분 안에 풀 수 있으면 Linked List 면접은 합격권!

image

시각 자료

다이어그램: ds-d40

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작