📕문제

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

문제 설명

링크드 리스트의 끝에서 n번째 노드를 제거하는 문제다.

예를들어 [1, 2, 3, 4, 5]가 주어지고 n이 2인 경우, 끝에서 2번째 노드인 4를 제거한 [1, 2, 3, 5]를 반환하면 된다.

---

📝풀이

투포인터

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        left, right = head, head

        for i in range(n):
            right = right.next
        
        if not right:
            return left.next

        while right.next:
            left = left.next
            right = right.next
        
        left.next = left.next.next
        
        return head

• head를 가리키는 left, head로부터 n칸 뒤 노드를 가리키는 right를 이용해 탐색한다.
• right이 None인 경우 left값을 제거한다는 뜻이므로 left.next를 반환한다.
• right가 리스트의 끝에 도달할 때 까지 두 포인터를 이동시킨다.
• right가 리스트의 끝에 도달했으면 right값이 끝에서 1번째라는 의미이므로 right의 n-1만큼 앞에 있는 노드를 제거한다.
  right - left = n
  right - (n-1) = left + 1
  즉 left.next값이므로 left.next 값을 left.next.next로 업데이트한다.