Labels

Tuesday, March 17, 2015

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.

Naive Way: Keep two pointers, let the second pointer move n step first. Then the gap between two pointers is n. Keep moving both pointers forward at same speed until second one reach the end. Then reconnect.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode removeNthFromEnd(ListNode head, int n) {  
     ListNode fake = new ListNode(0);  
     fake.next = head;  
     ListNode first = fake, second = fake;  
     // forward second by n  
     while(n-->0 && second.next!=null) second = second.next;  
     // edge case, length of linkedlist< n  
     if(n > 0){return head;}  
     // forward first and second till second reach the end  
     while(second.next!=null){  
       first = first.next;  
       second = second.next;  
     }  
     ListNode temp = first.next.next;  
     first.next = temp;  
     return fake.next;  
   }  
 }  

No comments:

Post a Comment