[LeetCode] Linked List 패턴 7개 치트시트

왜 Linked List 패턴 정리가 중요한가?

Linked List 문제를 많이 풀다 보면
문제는 달라 보여도 사고 흐름은 항상 비슷하다는 걸 느끼게 된다.

“포인터 이동 패턴을 이해하고 있는가?”

그래서 Linked List 문제를 패턴 단위로 묶어서 정리하기 시작했다.

---

🧠 Pattern 1. Slow / Fast Pointer (중간 찾기, 사이클)

언제 떠올릴까?

• “중간”/“절반”
• “사이클이 있는지”
• “한 번에 해결”

대표 문제

• Middle of the Linked List
• Linked List Cycle
• Reorder List
• Palindrome Linked List

 

핵심 아이디어

• slow: 1칸
• fast: 2칸

→ fast가 끝나면 slow는 중간

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

👉 “중간”이라는 단어가 보이면 자동으로 떠올려야 함

---

🧠 Pattern 2. Reverse Linked List (방향 뒤집기)

언제 떠올릴까?

• “뒤에서부터”
• “역순”
• “뒤쪽 접근 불가”
• “단일 리스트인데 tail이 필요할 때”

대표 문제

• Reverse Linked List
• Reorder List
• Palindrome Linked List
  
  

핵심 아이디어

• prev / curr / next

방향만 바꾸면 된다

ListNode prev = null;
ListNode curr = head;

while (curr != null) {
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
}

👉 단일 연결 리스트에서 뒤로 가고 싶으면 = reverse

---

🧠 Pattern 3. Two Pointer Gap (간격 유지)

언제 떠올릴까?

• “뒤에서 k번째”
• “n번째 전 노드”
• “한 번만 순회”

대표 문제

• Remove Nth Node From End
• Find kth node from end

핵심 아이디어

• 두 포인터 간격을 k로 유지
• fast 먼저 k칸 이동

for (int i = 0; i < k; i++) fast = fast.next;

while (fast != null) {
    slow = slow.next;
    fast = fast.next;
}

👉 “뒤에서” + “한 번에” = 간격 포인터

---

🧠 Pattern 4. Dummy Node (헤드 처리 단순화)

언제 떠올릴까?

• head가 바뀔 수 있음
• 삭제/삽입이 head 포함 가능
• 조건 분기 너무 많아질 때

대표 문제

• Remove Linked List Elements
• Merge Two Sorted Lists
• Add Two Numbers

핵심 아이디어

• 가짜 head 하나 두고 시작

ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode curr = dummy;

👉 “head 예외 처리 귀찮다” → dummy 쓰자

---

🧠 Pattern 5. Merge Two Lists (병합)

언제 떠올릴까?

• 두 리스트를 하나로
• 정렬된 리스트
• 교차 연결

대표 문제

• Merge Two Sorted Lists
• Reorder List (merge 단계)

핵심 아이디어

• 한 칸씩 비교
• 하나씩 연결

while (l1 != null && l2 != null) {
    if (l1.val < l2.val) {
        curr.next = l1;
        l1 = l1.next;
    } else {
        curr.next = l2;
        l2 = l2.next;
    }
    curr = curr.next;
}

 

---

🧠 Pattern 6. Stack / Recursion (뒤에서 접근 대안)

언제 떠올릴까?

• reverse를 쓰기 싫을 때
• 뒤에서부터 처리해야 할 때
• 공간 제약 없을 때

대표 문제

• Reorder List (stack 풀이)
• Palindrome Linked List

특징

• 구현 쉬움
• 공간 O(n)

👉 정석은 아니지만 사고 전개용으로 매우 유용

---

🧠 Pattern 7. Cycle Detection (Floyd’s Algorithm)

언제 떠올릴까?

• “사이클이 있나?”
• “무한 루프 가능성”
• “교차 지점”

대표 문제

• Linked List Cycle
• Linked List Cycle II

핵심 아이디어

• slow / fast가 만나면 사이클 존재

if (slow == fast) return true;

 

---

📌 패턴 요약 한 장 정리

문제 단서 떠올릴 패턴

• 중간 slow / fast
• 뒤에서 접근 reverse
• 뒤에서 k번째 gap pointer
• head 처리 복잡 dummy
• 두 리스트 합치기 merge
• 공간 여유 stack
• 사이클 slow / fast