[LeetCode] 19. Remove-nth-node-from-end-of-list 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Remove Nth Node From End of List 

---

문제 요약

연결 리스트에서 뒤에서 n번째 노드를 제거한 뒤 리스트를 반환하는 문제

 
문제링크: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

---

1. 처음 접근 방식

이 문제는 처음엔 직관적으로 이렇게 생각했다.

• 우선 리스트의 길이를 알아야 뒤에서 N번째가 어디 위치인지 알 수 있으므로
• 한 번 리스트를 끝까지 순회해서 길이를 구하고
• 다시 (길이 - n) 번째까지 가서 그 노드를 삭제

이 방법도 가능하지만,
👉 2번 순회가 필요해서 O(2N) 이라
👉 인터뷰에서 더 효율적인 풀이를 기대한다.
 
그래서 자연스럽게 이런 생각이 든다.

“리스트를 한 번만 돌고 해결할 수 없을까?”

 
 
다시 문제를 보자.
“끝에서 n번째”를 찾으려면... 2번째 아이디어를 떠올려야 한다.

• 1) 길이를 알아낸다  →  index로 접근한다
• 2) 길이를 모르지만  →  일정 거리 차이를 유지하도록 동시에 움직이면 된다.
  • 즉, 앞의 노드가 끝까지 갔을 때, n만큼 뒤에 있는 애가 삭제 대상
    

---

그래서 등장하는 풀이가 바로…
 

💡 핵심 아이디어

👉 Two Pointers (빠른 포인터 + 느린 포인터)

 
“뒤에서 n번째”라는 개념을
“앞에서 특정 거리 차이를 유지하는 두 포인터”로 바꿔서 해결하는 방법이다.
 

• fast = 먼저 달리는 애
• slow = 천천히 달리는 애

 

---

🚩 방법

 
“그럼 fast 를 얼마나 먼저 보낼까?”

• fast 포인터를 n칸 먼저 이동시킨다.
• 이후 slow 와 fast 를 함께 이동
• fast.next 가 끝(null)에 도달하면 → slow 는 “삭제할 노드의 이전 노드” 위치에 있다!
• slow.next = slow.next.next 로 삭제 완료

---

코드

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  public ListNode removeNthFromEnd(ListNode head, int n) {
    if(head == null) return null;

    ListNode slow = head;
    ListNode fast = head;
    while(n-- > 0){
      fast = fast.next;
    }
    if(fast == null) return head.next;
    while(fast.next != null){
      slow = slow.next;
      fast = fast.next;
    }
    slow.next = slow.next.next;
    return head;
  }
}

 
하지만 실제로는 edge case(특히 head 삭제)를 따로 처리해야 해서 깔끔하진 않다.
 
 

---

이를 dummy node 로 해결할 수 있다.

❗ 왜 Dummy Node 가 필요할까?

Linked List 삭제의 기본 규칙은 항상 이것이다.

“삭제할 노드의 이전(prev) 노드를 찾아
prev.next 를 건너뛰게 한다”

 
그런데 문제는… ❌ head 는 이전 노드가 없다
 
예) 1 → 2 → 3 → 4 → 5,  n = 5
삭제 대상 = head(1)

if (head 가 삭제 대상이면) head = head.next else 일반 삭제 로직

 
즉,  예외 처리 추가, 코드 복잡, 버그 유발

---

✅ Dummy Node 로 모든 게 깔끔해진다

1. “삭제는 항상 이전 노드가 필요하다”
2. “근데 head 는 이전 노드가 없다”
3. “그럼 head 도 이전 노드가 있게 만들면 되잖아?” → Dummy Node 탄생 🎉
   • 0(dummy) → 1 → 2 → 3 → 4 → 5
     
4. dummy 는 단순히 편하려고 쓰는 게 아니라 문제를 “예외 케이스 있는 문제 → 예외 없는 단일 규칙 문제”로 바꿔준다.

 

---

최종 코드 (Java / Dummy + Two Pointer)

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode dummy = new ListNode(0, head);
        ListNode fast = head;
        ListNode slow = dummy;

        // fast 를 n 만큼 먼저 이동
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // fast 끝까지 → slow 는 삭제 이전 지점 도착
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 삭제
        slow.next = slow.next.next;

        return dummy.next;
    }
}
/*
//혹은 이렇게도 가능
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;

        // fast 를 n 만큼 먼저 이동
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // fast 끝까지 → slow 는 삭제 이전 지점 도착
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 삭제
        slow.next = slow.next.next;

        return dummy.next;
    }
}
*/

---

📈 Time / Space Complexity

시간: O(n) (리스트 한 번 순회)
공간: O(1)

---

📝 이번 문제에서 얻은 깨달음

• Two Pointer 는 “속도”가 아니라 👉 “상대적인 거리 유지” 가 핵심이다.
• 리스트 조작 문제에서 rule-of-thumb 👉 “head 가 특별 취급되어 if 문이 생기면 → Dummy Node 를 고려하자”

• Dummy Node 는 단순 편의 도구가 아니라 문제를 구조적으로 단순화하는 강력한 도구

• 같은 O(n)이라도
  • ✔ 예외 처리 없이
  • ✔ 깔끔하고
  • ✔ 안정적인 코드가 진짜 좋은 코드이다.