[Leetcode/Two Pointer] 19. Remove Nth Node From End of List

 

이 문제를 한 번의 순회(One-pass)로 해결하는 방법은 두 개의 포인터(first, second)를 사용하는 것이다.
first 포인터를 먼저 n칸 이동시킨 후, second 포인터를 first와 함께 이동하면 first가 끝에 도달했을 때 second는 삭제할 노드의 직전 노드를 가리키게 된다.

✅ 알고리즘 풀이 (Two Pointer)

1. 더미 노드 추가: 삭제할 노드가 head일 수도 있으므로 더미 노드를 추가.
2. first 포인터 선행 이동: first를 n칸 먼저 이동.
3. 두 포인터 이동: first가 리스트의 끝에 도달할 때까지 second와 함께 이동.
4. 노드 삭제: second.next를 second.next.next로 변경하여 노드 삭제.
5. 새로운 head 반환: dummy.next를 반환.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0)  # ① 더미 노드를 생성하여 head를 감싸줌 (삭제할 노드가 head일 수도 있기 때문)
        dummy.next = head
        first = dummy
        second = dummy

        # ② first 포인터를 n+1 칸 이동 (second와 n칸 차이를 만들기 위해)
        for i in range(n + 1):
            first = first.next
        
        # ③ first가 리스트 끝까지 가도록 first, second 함께 이동
        while first is not None:
            first = first.next
            second = second.next

        # ④ second.next가 삭제할 노드이므로 건너뛰도록 변경
        second.next = second.next.next

        # ⑤ 새로운 head 반환
        return dummy.next

 

⏳ 시간 복잡도 분석

• O(N): 리스트를 한 번만 순회하므로 O(N)의 시간 복잡도를 가짐.
• O(1): 추가적인 공간을 거의 사용하지 않음.

 

https://leetcode.com/problems/remove-nth-node-from-end-of-list/