Remove Nth Node From End of List | Leetcode

Given a linked list, remove the n^th 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.

---

Solution: Keep a node that skips n nodes first. Keep another node that starts from the head node. Advance both nodes at the same time until the first node reaches the end of the list. The second node will now point to the nth node. Remove the nth node and return the head of the list as the answer.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node = head;
        
        for (int i = 0; i < n; i++) {
            node = node.next;
        }
        
        if (node == null) return head.next;

        node = node.next;        
        ListNode prev = head;
        
        while (node != null) {
            prev = prev.next;
            node = node.next;
        }
        
        prev.next = prev.next.next;
        return head;
    }
}