[Two Pointers] 19. Remove Nth Node From End of List

문제 링크 

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

 

문제 접근 방법

 

투포인터의 응용 문제이다.

tail으로부터 출발하면 투포인터 쓰지 않아도 되지 않나...생각했는데, 투포인터를 쓴대니까 right pointer로 삭제할 노드를 짚어내나? 라고 생각해서 접근했는데 이렇게는 도무지 투포인터 패턴으로 문제가 안풀리는거다.

 

일단 left pointer의 역할은 연결리스트 특성상 노드를 삭제하고 나면 삭제된 노드 이전 노드랑 연결하는 역할일거라 생각해서, left pointer는 루프가 끝났을 때 무조건 그 곳으로 가있어야할 것 같았고.. (즉, Nth Node - 1에 위치하고 있어야함) 

그럼 left/right pointer 둘 중 어떤 걸로 삭제할 Nth Node를 짚어내나? 어떻게 하지..? 생각했는데 일단 right 포인터가 완전 tail으로 이동했다고 생각했을 때, left pointer와 right pointer가 주어진 n만큼 벌어져있으면 자연스럽게 left pointer는 삭제할 Nth Node에 위치할 것이라고 나왔다.

 

 

The optimized two-pointer approach removes the Nth node from the end of a linked list in one traversal by maintaining a fixed gap between two pointers. Initially, both left and right pointers start at the head, and the right pointer is moved forward by n steps, creating a gap of n nodes. This gap ensures that when the right pointer reaches the end of the list, the left pointer is positioned just before the node to be removed. Both pointers then move forward together, maintaining the gap, until the right pointer reaches the end. At this point, the target node is skipped by updating the left pointer’s next link. If the right pointer reaches the end during the initial nn steps, it indicates the head node is the target, which is removed by returning the next node of the head.

 

 

1. Initialize two pointers, left and right, both pointing to the head of the linked list.
2. Move the right pointer n steps ahead. This creates a gap of n nodes between the left and right pointers.
3. If, after moving the right pointer n steps forward, it becomes NULL, it means the head node is the target for removal. In this case, return head.next as the new head of the linked list, effectively removing the original head node.
4. If the right pointer hasn’t reached the end after moving n steps, move both the right and left pointers forward by one step at a time, maintaining the gap between them. This ensures that when the right pointer reaches the end of the linked list, the left pointer will be positioned just before the node that needs to be removed.
5. Once the right pointer reaches the end of the linked list, update left.next to left.next.next. This action skips over the target node, effectively removing it from the linked list.
6. Finally, return the original head, which now points to the updated linked list with the nth node removed.

pc: educative

 

pc: educative

pc: educative

pc: educative

pc: educative

 

고민한 부분, 주의사항

출처: eductive

example 4에서, 만약에 내가 삭제해야하는 Nth Node가 head인 경우의 테스트 케이스를 처리해주지 않아서 통과를 안하는거다!

세운 알고리즘 대로라면, gap으로 벌린 n이 너무 커서 right pointer가 Null으로 넘어가는 경우(if not right)에는 head를 버리는 거니까 head 이후의 노드들을 반환하는 경우도 처리를 해주어야 했다. 

 

  if not right:
      return head.next

 

코드

# Definition for a Linked List node
# class LinkedListNode:
#     def __init__(self, data, next=None):
#         self.data = data
#         self.next = next

from linked_list import LinkedList
from linked_list_node import LinkedListNode

def remove_nth_last_node(head, n):
    left = right = head 
    for i in range(n):
      right = right.next
      
    if not right: # n의 크기가 연결리스트 크기만큼 큰 바람에 right가 None으로 벗어나서, head node를 없애야 하는 경우 
      return head.next
      
    while right.next:
      left = left.next
      right = right.next
    
    left.next = left.next.next
      
    
    return head

 

 

풀고 나서 (접근법, 사용되는 알고리즘 개념)