19. Remove Nth Node From End of List

// LeetCode URL: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

//   Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

/**
 * Two pointer.
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(1)
 *
 * N = Length of input list.
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }

        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode fast = dummyNode;
        ListNode slow = dummyNode;

        while (n > 0) {
            if (fast.next == null) {
                return head;
            }
            fast = fast.next;
            n--;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        ListNode toBeRemoved = slow.next;
        slow.next = toBeRemoved.next;
        toBeRemoved.next = null;

        return dummyNode.next;
    }
}