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.

This is not the best solution but still O(n) time, also it is only one iteration, which is the try to part of the note.


/**
 * 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) {
        
        if(head == null || (head.next == null && n == 1)){
            return null;
        }
        
        ArrayList bucket = new ArrayList();
        
        ListNode position = head;
        
        while(position != null){
            bucket.add(position);
            position = position.next;
        }
        
        int length = bucket.size();
        
        if(length-n <= 0){
            head = head.next;
        }else if(bucket.get(length-n) == null || bucket.get(length-n).next == null){
            bucket.get(length-n-1).next = null;
        }else{
            bucket.get(length-n-1).next = bucket.get(length-n+1);
        }
        
        return head;
        
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s