# Two pointers and Linked List

# 19. Remove Nth Node From End of List

## The two-pass solution

The two-pass solution is relatively easier. We traverse the list and find the total number of nodes for this list say N. Then the last n element will be the first N- n

`# 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: ListNode, n: int) -> ListNode:

dummy = ListNode(-1)

dummy.next = head

node = dummy

N = 0

while node:

N += 1

node = node.next

node = dummy

for _ in range(N-n-1):

node = node.next

node.next = node.next.next

return dummy.next

## The one-pass solution

The key observation is using two pointers to record the location difference. From the final states, if the first pointer points to the tail which is Null, then the second pointer should point to the previous node of the to be deleted node. The distance between the first pointer and the second pointer will be n+1.

How can we maintain this distance?

Put the second point at the head, move the first pointer ahead by (n+1) steps, then the distance between the first pointer and the second pointer will be n+1. After that, move both two pointers together. By doing this, we can make sure that the distance between the first pointer and the second pointer will be exactly n+1. When the first pointer reaches the tail, the first pointer will point to the previous node of ‘to be deleted node’.

Delete it by using prev.next = prev.next.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: ListNode, n: int) -> ListNode:

dummy = ListNode(-1)

dummy.next = head

first = second = dummy

for _ in range(n+1):first = first.next

while first:

first = first.next

second = second.next

second.next = second.next.next

return dummy.next

# Reference

[1]https://leetcode.com/problems/remove-nth-node-from-end-of-list/solution/