Remove Nth Node From End of List

Question: Given a linked list, remove the n-th node from the end of list and return its head.

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.

You may view the full question here.

Approach 1: Here is a simple approach using a list —

//Approach 1
//Runtime: 1ms
//Memory usage: 36.9MB
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<ListNode> list = new ArrayList();
        ListNode curr = head;
        while(curr!=null){
            list.add(curr);
            curr = curr.next;
        }
        int size = list.size();
        if(size>1){
            if(size>n){
                ListNode prev = list.get(size-n-1);
                ListNode next = null;
                if(n>1){
                    next = list.get(size-n+1);
                }
                prev.next = next;
            } else {
                head = list.get(1);
            }
            return head;
        }
        return null;
    }
}

Approach 2: After borrowing some ideas from THE source, here is what a one pass solution looks like —

//Approach 2:
//Runtime: 0ms
//Memory usage: 36.9MB
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode curr = head;
        for(int i = 0; i<n && curr!=null; i++){
            curr = curr.next;
        }
        ListNode nNode = head;
        ListNode prevNode = null;
        while(curr!=null){
            prevNode = nNode;
            nNode = nNode.next;
            curr = curr.next;
        }
        if(prevNode!=null){
            prevNode.next = nNode.next;
            return head;
        } else {
            return nNode.next;
        }
    }
}

Find more posts here.

Cheers & Chao!