0019 - Remove Nth Node From End of List (Easy)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

// Time Complexity: O(N) where N is the number of nodes
// Space Complexity: O(1)
class Solution {
public:
    // the general idea is to use fast & slow pointers
    // 1. traverse L - n nodes from the start of the list using fast pointer
    // where L is the length of the linked list
    // e.g. in example 1, the fast pointer will be at node 3 while slower pointer remains at node 1
    // 2. traverse slow pointer until fast pointer reaches the last node
    // e.g. in example 1, the fast pointer will be at node 5 while slower pointer will be at node 3
    // 3. update slow next node
    // e.g. in example 1, the slower pointer is at node 3 now. we link the next node to node 5.
    // therefore, we have 1 -> 2 -> 3 -> 5 at the end
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* slow = head;
        ListNode* fast = head;
		// move fast pointer to the n + 1 element
        // now the distance between slow and fast pointer is n nodes
        while (n--) fast = fast->next;
        // if fast reached the end, we need to remove the first element
        // e.g. head = [1], n = 1
        if (fast == nullptr) return head->next;
        // move both pointers at the same time until the fast pointer reaches the end
        while (fast->next != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        // slow pointer will be pointing to the node before the one to be removed
        // then we update the next node of the slow pointer
        slow->next = slow->next->next;
        return head;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Dummy head pointer to return head reference at the last
        ListNode current = new ListNode();
        current.next = head;
        // Initialize slow and fast pointer to dummy head
        ListNode slow = current, fast = current;
        while (fast.next != null) {
            fast = fast.next;
            if (n <= 0) {
                slow = slow.next;
            }
            n -= 1;
        }
        slow.next = slow.next.next;
        // Head reference
        return current.next;
    }
}