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
Given a linked list:

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

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
    
    def __str__(self):
        head = self
        ans = ''
        while head != None:
            ans = ans + str(head.val)
            head = head.next
            if head != None:
                ans = ans + '->'

        return ans


class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        i = head
        j = head

        # 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
            head = head.next

        return head


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

    solution = Solution()
    print(solution.removeNthFromEnd(head, 2))

    head = ListNode(1)
    print(solution.removeNthFromEnd(head, 1))

    head = ListNode(1)
    head.next = ListNode(2)
    print(solution.removeNthFromEnd(head, 2))

if __name__ == "__main__": main()