19. Remove Nth Node From End of List Leetcode Java

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.

Solution:

walker-runner trick.

This is commonly used in linked list problems. Runner is a pointer transverse the list faster or earlier. In this problem, runner is n positions earlier than walker, so when runner hits the end of the list, while walker is (n+1)th node from the end of the list, the previous node of nth node that we try to delete. In order to delete a specific node,we have to find the previous one in singly linked list. By this technique, we can delete the unwanted node only in one pass.

Time complexity: O(n)

 public ListNode removeNthFromEnd(ListNode head, int n) {  
     if(n<=0) return head;  
    ListNode predummy=new ListNode(0);  
    predummy.next=head;  
    ListNode walker=predummy;  
    ListNode runner=predummy;  
    for(int i=0;i<n&& runner!=null;i++) runner=runner.next;  
    if(runner==null) return head;  
    while(runner.next!=null){  
      walker=walker.next;  
      runner=runner.next;  
    }  
    ListNode temp=walker.next;  
    walker.next=temp.next;  
    temp.next=null;  
    return predummy.next;  
   }