Question:

Given a singly linked list, remove the n-th node from the end of the list and return its head.

Note: You may assume that n is always valid and that the list does not contain any cycles.

Example:

Input:

1 -> 2 -> 3 -> 4 -> 5

n = 2

Output:

1 -> 2 -> 3 -> 5

Constraints:

• The number of nodes in the list is between 1 and 30.
• The value of each node in the list is between 1 and 100.
• n is a valid integer.

Answer:

To solve this problem, we need to find the nth node from the end of the linked list and remove it. There are a few steps involved in the solution:

1. Initialize two pointers, fast and slow, pointing to the head of the linked list.
2. Move the fast pointer to the n+1-th node from the head.
3. Move both fast and slow pointers one step at a time until the fast pointer reaches the end of the list.
4. At this point, the slow pointer will be pointing to the n-th node from the end.
5. Remove the n-th node by adjusting the next pointer of the previous node to skip the n-th node.
6. If the slow pointer is pointing to the head, update the head of the list accordingly.

Here is the implementation in Python:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head, n):
    # Create a dummy node to handle edge case of removing the head node
    dummy = ListNode(0)
    dummy.next = head

    fast = dummy
    slow = dummy

    # Move the fast pointer to the n+1-th node from the head
    for _ in range(n+1):
        fast = fast.next

    # Move both pointers until the fast pointer reaches the end
    while fast != None:
        fast = fast.next
        slow = slow.next

    # Remove the n-th node by adjusting the next pointer of the previous node
    slow.next = slow.next.next

    # Update the head of the list if necessary
    if slow == dummy:
        return dummy.next

    return head

# Example usage:
# Create the linked list: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

n = 2
result = removeNthFromEnd(head, n)
# The new list after removing the 2nd node from the end: 1 -> 2 -> 3 -> 5

The time complexity of this solution is O(L), where L is the length of the linked list. We traverse the list twice, once to find the n+1-th node from the head, and then to find the n-th node from the end.