Remove Nth Node From End of a Linked List

This problem challenges you to manipulate a singly linked list. Given a linked list and an integer n, you must delete the nth node from the end of the list and return the head of the modified list. This is a common interview question that tests your understanding of linked list traversal and manipulation.

Problem Description

You are given a singly linked list and an integer n. Your task is to remove the nth node from the end of the list. The list is represented as a sequence of nodes, where each node has a value and a next pointer pointing to the next node in the list (or null if it's the last node).

What needs to be achieved:

• Identify the nth node from the end of the list.
• Remove that node from the list.
• Return the head of the modified list.

Key Requirements:

• The list may be empty.
• n will always be a valid positive integer.
• You must handle the case where n is equal to the length of the list (i.e., removing the head).
• You must handle the case where n is greater than the length of the list (should not happen given the constraints, but good to consider).

Expected Behavior:

The function should modify the linked list in-place and return the head of the modified list. The list should remain a valid singly linked list after the removal.

Edge Cases to Consider:

• Empty list.
• List with only one node.
• n is equal to the length of the list (remove the head).
• n is 1 (remove the last node).

Examples

Example 1:

Input: [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]
Explanation: The second node from the end is 4. Removing it results in the list [1, 2, 3, 5].

Example 2:

Input: [1], n = 1
Output: []
Explanation: The only node in the list is the first (and only) node. Removing it results in an empty list.

Example 3:

Input: [1, 2], n = 1
Output: [1]
Explanation: The first node from the end is 2. Removing it results in the list [1].

Constraints

• The number of nodes in the list will be between 1 and 10⁵.
• n will be between 1 and the length of the list.
• The values of the nodes will be integers.
• The solution should have a time complexity of O(N), where N is the number of nodes in the list. Space complexity should be O(1).

Notes

A common approach to solve this problem efficiently is to use two pointers. One pointer can be advanced n nodes ahead of the other, and then both pointers can be moved forward simultaneously until the second pointer reaches the end of the list. The node before the second pointer will be the node to be removed. Consider how to handle the case where you need to remove the head of the list. Remember to update the next pointer of the previous node correctly.