5. 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.

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?

Approach - 2 pointer

• Create left and right pointer and left pointing to a block before head and right pointing to the nth element
• Left pointer to a new block because if you start with head you will reach the exact element but we need to reach an element before that
• Shift right pointer to the right to the nth node so as to create a window then loop till it reaches null and move left pointer too it will reach n-1 node from last then it is simple
• Time:O(n) Space:O(1)

/**
 * 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) {
        ListNode dummy = new ListNode(0, head);
        ListNode left = dummy;
        ListNode right = head;
 
        while (n > 0) {
            right = right.next;
            n--;
        }
 
        while (right != null) {
            left = left.next;
            right = right.next;
        }
 
        left.next = left.next.next;
        return dummy.next;  // cannot return head as [1] should return []
    }
}