Leetcode 19 : Remove nth Node from end of List

Problem Statement

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

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Test Cases

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:

Input: head = [1], n = 1
Output: []
Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints

The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

Follow up: Could you do this in one pass?

Intuition

We need to know the previous node of the targeted node we will delete, ie nth node from the end, and then we can shift the position of the previous node two places front.
We must be aware that if n value is the total length of the linked list, then it is the first node that we want to delete, and we can just shift the head to the next node.

Approach

• Use 2 pointers, slow, fast.
• We move the pointer fast until n > 0, so that we can get a gap of n elements between slow and fast.
• Move the fast pointer to the next pointer and again traverse until fast is null.
• This time, also move the slow pointer so that when fast is null, the slow pointer would reach the previous node of the targeted node.
• Now move the next of slow pointer to next of the targeted node.

Complexity

• Time complexity:

O(N) - as we are traversing the linked list only once, this is a one-pass solution.

• Space complexity:

O(1) as there is no extra space used.

Code

/**
 * 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) {
        if (head == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (n-- > 0) {
            fast = fast.next;
        }
        if (fast == null) {
            // meaning deleting first number
            return head.next;
        }
        fast = fast.next;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}