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.

Solution:

Use two pointers, from the beginning go N-1 steps, fine the pre pointer of Nth, then go until this pointer reaches end, then the other pointer starting from head will reach the N-1th element.

Points to remember:

1. To remove Nth node, we need Pre node, i.e., N+1th Node

2.1st node is the last node, there is no pointer moving.

Code:

    ListNode* st=head;
    ListNode* ed=head;
    ListNode* pre=head;
    if (!head) return NULL;
    if (!head->next)
    {
        if (n==1) return NULL;
        else
            return head;
    }

    int i=1;
    while(inext;
        i++;
    }
    ed = head;

    if (!st->next)
    {
        head = head->next;
        delete ed;
        return head;
    }

    while(st->next->next)
    {
        ed = ed->next;
        st= st->next;
    }

    pre=ed;
    st = ed->next;
    pre->next = st->next;
    delete st;
    return head;