Remove Nth Node From End Of List - Leetcode Solution

The problem "Remove Nth Node From End Of List" on LeetCode asks us to remove the n-th node from the end of a singly linked list and return the modified list. In other words, given a linked list and an integer n, we have to remove the node from the list that is n positions away from the end of the list.

The input to the problem is a linked list represented as a chain of nodes, where each node has two fields: a value field that contains the node's data, and a next field that contains a pointer to the next node in the list. The last node of the linked list has a next field that is NULL.

The output of the problem should be the modified linked list, where the n-th node from the end has been removed.

We can solve this problem using a two-pass algorithm, where in the first pass we count the total number of nodes in the list, and then in the second pass we remove the n-th node from the end of the list.

Here is the detailed solution using this algorithm:

1. Initialize two pointers, current and temp, to the head of the linked list.
2. Traverse the list using current pointer to count the number of nodes in the list. Let the count be N.
3. Compute the position of the node to be removed as (N - n + 1), where n is the given input.
4. If the position is 1, remove the head node and return the modified linked list.
5. If the position is greater than 1, set the temp pointer to the node at position (position - 1).
6. Set the next field of the node pointed to by temp to the node pointed to by the next field of temp.
7. Return the modified linked list.

Here is the implementation of the above algorithm in Python:

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

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    # Step 1: Initialize pointers current and temp to the head of the linked list
    current = head
    temp = head
    # Step 2: Traverse the list to count the number of nodes in the list
    count = 0
    while current:
        count += 1
        current = current.next
    # Step 3: Compute the position of the node to be removed
    position = count - n + 1
    # Step 4: If the position is 1, remove the head node and return the modified linked list
    if position == 1:
        return head.next
    # Step 5: If the position is greater than 1, set the temp pointer to the node at position (position - 1)
    for i in range(position - 2):
        temp = temp.next
    # Step 6: Set the next field of the node pointed to by temp to the node pointed to by the next field of temp
    temp.next = temp.next.next
    # Step 7: Return the modified linked list
    return head

The time complexity of this solution is O(n), where n is the number of nodes in the linked list, since we do a two-pass traversal of the list. The space complexity is O(1), since we use a constant amount of extra memory.

1