Day 60: Python으로 Linked List 끝에서 N번째 노드 제거, 한 번에 삭제하는 Two-Pointer 매직 (LeetCode #19 스타일)

Source: Dev.to

Day 60 – 연결 리스트 끝에서 N번째 노드 제거

#80DaysOfChallenges 여정의 Day 60에 오신 것을 환영합니다! 이 중급 챌린지는 유명한 Remove Nth Node From End of Linked List 문제(LeetCode #19)를 두 포인터 기법을 사용해 한 번의 순회로 목표 노드를 찾아 삭제하며, 추가 공간을 O(1)만 사용합니다. 솔루션에는 Node 클래스, 연결 리스트를 만들고 출력하는 헬퍼 함수, 그리고 인터랙티브 테스트를 위한 main 루틴이 포함됩니다.

예시
리스트 1 → 2 → 3 → 4 → 5, n = 2 → 1 → 2 → 3 → 5 (끝에서 두 번째 노드인 4를 삭제)

핵심 포인트

Node 클래스와 빌더: 손쉬운 리스트 생성

class Node:
    """Simple singly linked list node."""
    def __init__(self, value: int):
        self.value = value
        self.next = None

def build_linked_list(values: list[int]) -> Node:
    """Build a linked list from a list of integers."""
    if not values:
        return None

    head = Node(values[0])
    curr = head
    for v in values[1:]:
        curr.next = Node(v)
        curr = curr.next
    return head

O(n) 시간에 리스트를 만들며, 빈 입력 리스트도 정상적으로 처리합니다.

삭제 함수: 더미 헤드와 두 포인터 활용

def remove_nth_from_end(head: Node, n: int) -> Node:
    """
    Remove the Nth node from the end using fast/slow pointers.
    Returns the new head after deletion.
    """
    dummy = Node(0)          # Simplifies edge cases (e.g., deleting the head)
    dummy.next = head
    fast = dummy
    slow = dummy

    # Move fast pointer n+1 steps ahead
    for _ in range(n + 1):
        if fast is None:
            return head      # n is larger than the list length
        fast = fast.next

    # Advance both pointers until fast reaches the end
    while fast is not None:
        fast = fast.next
        slow = slow.next

    # Delete the target node
    slow.next = slow.next.next
    return dummy.next

더미 노드를 사용하면 헤드 삭제와 같은 특수 경우를 별도로 처리할 필요가 없습니다. fast 포인터를 n+1칸 앞으로 이동시킴으로써 slow가 삭제할 노드 바로 앞에 위치하게 되어, 한 번의 순회로 O(n) 해결이 가능합니다.

프린터와 메인: 시각화 및 입력 처리

def print_linked_list(head: Node) -> None:
    """Print linked list values cleanly."""
    curr = head
    nodes = []
    while curr is not None:
        nodes.append(str(curr.value))
        curr = curr.next
    print(f"Linked List: {' -> '.join(nodes)}")

# Interactive demo
raw_nums = input("Enter list values (space-separated): ").strip()
raw_n = input("Enter n (which node from the end to remove): ").strip()

if not raw_nums or not raw_n:
    print("Invalid input. Exiting.")
    exit()

nums = list(map(int, raw_nums.split()))
n = int(raw_n)

head = build_linked_list(nums)
print("Original list:")
print_linked_list(head)

new_head = remove_nth_from_end(head, n)
print(f"List after removing {n}th node from the end:")
print_linked_list(new_head)

스크립트는 공백으로 구분된 정수를 파싱하고, 리스트를 만든 뒤 원본 구조를 출력합니다. 그 후 삭제를 수행하고 결과 리스트를 보여줍니다.

요약 및 회고

이 문제는 단일 연결 리스트의 끝에서부터 요소에 접근하기 위해 길이를 미리 계산하지 않아도 되는 두 포인터 기법의 우아함을 보여줍니다.

• 더미 헤드 활용 – 헤드 삭제 시 발생하는 엣지 케이스를 없앱니다.
• 포인터 간격 – fast를 n+1칸 앞에 두면 slow가 정확히 목표 노드 앞에 위치합니다.
• 한 번의 순회 효율성 – 시간 복잡도 O(n), 추가 공간 O(1).

재귀적 접근도 가능하지만, 깊은 리스트에서는 반복적 풀이가 더 안전합니다.

다음 단계 및 참고 자료

• 챌린지 #60 소스 코드 – scripts/remove_nth_from_end.py
• 전체 저장소 – 80-days-of-challenges
• 일일 업데이트 – Twitter/X (@Shahrouzlogs)