## fizzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Remove Nth node from end of list

Sharing is caring!

Problem statement

class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

remove the $n^{th}$ node from the end of list and return its head.

Sample input

1->2->3->4->5
2

Sample output

1->2->3->5

Note: $n$ will always be valid.

Solution
For this we will use a two pointer technique. That is, we will iterate over our list using two pointer $i$ and $j$. First, we will fast-forward $j$ $n$ positions. That is, $j$ will be $n$ nodes ahead of $i$.

We will then iterate over the list using $i$ and $j$ by pointing them to the next nodes one-by-one. When $j$ reaches the end of the list, we will know that $i$ will point to the $(n+1)^{th}$ node from the end of list. We will then adjust the next pointers accordingly and return the head of the list.

Full code

class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

def __str__(self):
ans = ''
ans = ans + '->'

return ans

class Solution(object):
"""
:type n: int
:rtype: ListNode
"""

# Fast forward j n positions
for count in range(0,n):
j = j.next

# Iterate over the list one by one until j hits the end
while j != None and j.next != None:
j = j.next
i = i.next

# j reached the end. This means i points to the (n+1)th node from the end of list (since j was n nodes ahead)
if j != None:
i.next = i.next.next
else:
# Remove i itself

def main():
for x in range(2, 6):
node.next = ListNode(x)
node = node.next

solution = Solution()