Remove Nth Node From End of List

Question

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: **1->2->3->4->5**, and **n = 2**.

   After removing the second node from the end, the linked list becomes **1->2->3->5**.

Note: Given n will always be valid. Try to do this in one pass.

Tags

• Linked List
• Two Pointers

Thought

Use two pointers algorithm:

1. Both of the two pointers are initialized at the dummy node before the head node.
2. Move the first pointer N steps.
3. Then move two pointers same steps in the while loop until the next variable of the first pointer is none. The next variable of the second pointer is the node need to be removed.

Code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        # http://www.cnblogs.com/zuoyuan/p/3701971.html
        dummy = ListNode(0)
        ptr1 = ptr2 = dummy
        dummy.next = head
        for i in xrange(n):
            ptr1 = ptr1.next
        while ptr1.next:
            ptr1 = ptr1.next
            ptr2 = ptr2.next
        ptr2.next = ptr2.next.next
        return dummy.next