Leetcode: 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.

Hide Tags

 Linked List Two Pointers

------------------------------------------

------------------------------------------

Using two pointers: late, pre:

pre goes forward for n steps then move both pointers forward until pre reaches the end. Then the late is the location we want. There are two cases in this method, when in the final, the late is the first node and when late is non-first node:

/////////////////////////////////////////////////

//codes

class Solution {

public:

       ListNode* removeNthFromEnd(ListNode* head, int n) {

              //check input

              if (head == NULL)return head;

              ListNode *pre = head, *late = head;

              //move the pre n node ahead

              for (int i = 0; i<n &&pre != NULL; i++){

                     pre = pre->next;

              }

              //if the head would be deleted

              if (pre == NULL) {

                     head = head->next;

                     delete late;

                     return head;

              }

              //move two pointer forward with n interval

              while (pre->next != NULL){

                     pre = pre->next;

                     late = late->next;

              }

              //delete the the one in late->next

              pre = late->next->next;

              delete late->next;

              late->next = pre;

              return head;

       }

};