Monday, January 5, 2015

Remove Nth Node From End of List (LeetCode Linked List)

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

Idea: First add a dummy head at the front of the input linked list, since the original head may be the node to be removed. Then use two pointers "slower" and "faster" to traverse the list. Let the faster run n steps, then let the faster and the slower run simultaneously. Since the faster is n steps ahead of the slower, when faster.next reach the end (null), the slower.next is the nth node which needs to be removed.

Time: O(n) Space: O(1)

Code: 
 public class Solution {  
   public ListNode removeNthFromEnd(ListNode head, int n) {  
     ListNode dummy=new ListNode(0);  
     dummy.next=head;  
     ListNode slower=dummy;  
     ListNode faster=dummy;  
     for(int i=0;i<n;i++)  
       faster=faster.next;  
     while(faster.next!=null)  
     {  
       slower=slower.next;  
       faster=faster.next;  
     }  
     slower.next=slower.next.next;  
     return dummy.next;  
   }  
 }  

No comments:

Post a Comment