Remove Nth Node from End of List

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.

We are given the ListNode class

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

First, let's set two pointers to go through the linked list.

class Solution(object):
    def removeNthFromEnd(self, head, n):
        needle = head
        end = head

Then, we want to move the end pointer past the needle pointer by n steps. After that we move both pointers until end is the last node of the linked list.

        for i in range(n-1):
            end = end.next

        while end.next != None:
            needle = needle.next
            end = end.next

Notice that needle pointer will always be n steps behind the end pointer. Thus, when the end pointer is at the last node, the needle pointer is pointing at the (n+1)th last node. From there, we drop out the nth to last node by setting needle.next to the next next node.

        needle.next = needle.next.next
        return head

We can always change it return the value of the head through head.val. Now we can test it out using this:

numbers = ListNode(1)
numbers.next = ListNode(2)
numbers.next.next = ListNode(3)
numbers.next.next.next = ListNode(4)
n = 2
sol = Solution()
print sol.removeNthFromEnd(numbers, n)

This question is quite similar to this that I've done some time back. It's in a different language though(C).