Remove Nth Node From End of List

Remove Nth Node From End of List

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

Example

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

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

Solution

从头开始走， 可以走到右面第N个的前一个。

set up two pointers , one is fast pointer and second is the slower pointer, the fast pointer go to N , then slow pointer start to until fast pointer is done.

for i in range(n):

    if head == None:

        return None

    head = head.next



    from head move it to n steps/

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param head: The first node of linked list.
    @param n: An integer.
    @return: The head of linked list.
    """
    def removeNthFromEnd(self, head, n):
        # write your code here
        if n <= 0:
            return head
        dummy = ListNode(0)
        dummy.next = head

        preDelete = dummy

        for i in range(n):
            if head == None:
                return None
            head = head.next
        while head:
            head = head.next
            preDelete = preDelete.next

        preDelete.next = preDelete.next.next

        return dummy.next