Find the nth Node from the end of a Linked List

The problem of finding the nth node from the end of a linked list involves finding the node that is n positions away from the end of the linked list.

For example, if the linked list has 10 nodes and n is 3, we need to find the 3rd node from the end of the list, which would be the 8th node from the beginning of the list.

One approach to solving this problem is to first traverse the linked list to determine its length. Once we know the length of the linked list, we can calculate the position of the nth node from the end by subtracting n from the length of the list.

We can then traverse the list again, this time stopping at the node that is n positions away from the end.

Another approach to solving this problem involves using two pointers, where one pointer starts at the head of the linked list and the other pointer starts n nodes ahead.

We then move both pointers simultaneously until the second pointer reaches the end of the list. At this point, the first pointer will be pointing to the nth node from the end of the list.

We can also use recursion to solve this problem. In this approach, we recursively traverse the linked list until we reach the end. Once we reach the end of the list, we start counting backwards from n.

1: Find the nth Node: Traverse the linked list to determine its length

The solution involves three steps. In the first step, we traverse the linked list to determine its length.

In the second step, we calculate the position of the nth node from the end by subtracting n from the length of the list.

Finally, in the third step, we traverse the list again, this time stopping at the node that is n positions away from the end.

The time complexity of this solution is O(n), where n is the number of nodes in the linked list, since we need to traverse the linked list twice in the worst case.

The space complexity is O(1), since we only need a constant amount of extra space to store variables.

def nth_node_from_end(head, n):
    # Step 1: Traverse the linked list to determine its length
    length = 0
    curr = head
    while curr:
        length += 1
        curr = curr.next

    # Step 2: Calculate the position of the nth node from the end
    position = length - n

    # Step 3: Traverse the linked list again, stopping at the nth node from the end
    curr = head
    for i in range(position):
        curr = curr.next

    return curr

2: Find nth Node: Use two pointers to traverse the list

This approach involves using two pointers, where one pointer starts at the head of the linked list and the other pointer starts n nodes ahead.

We then move both pointers simultaneously until the second pointer reaches the end of the list. At this point, the first pointer will be pointing to the nth node from the end of the list.

The time complexity of this solution is O(n), where n is the number of nodes in the linked list, since we need to traverse the linked list once in the worst case. The space complexity is O(1),

since we only need a constant amount of extra space to store variables.

def nth_node_from_end(head, n):
    # Step 1: Move the first pointer n nodes ahead of the head
    first = head
    for i in range(n):
        if first:
            first = first.next
        else:
            return None

    # Step 2: Move both pointers simultaneously until the first pointer reaches the end
    second = head
    while first:
        first = first.next
        second = second.next

    return second

3: Find nth Node in Linked List using Recursion

In the recursive approach, we define a recursive function that takes in the head of the linked list and the value of n. The function returns the nth node from the end of the linked list.

The base case of the recursive function is when the head is None, which means we’ve reached the end of the list. In this case, we return None.

The recursive step involves calling the function recursively with the next node in the list as the new head. Once we reach the end of the list, the current_node variable will be None.

Once we’ve reached the end of the list, we start counting backwards from n by using a count variable. If the count variable is equal to n, we return the current node as the nth node from the end. If the count variable is less than n, we return None.

The time complexity of the recursive approach is O(n), where n is the number of nodes in the linked list, since we need to traverse the entire list in the worst case.

The space complexity of the recursive approach is also O(n), since the function call stack can have up to n frames in the worst case.

def nth_node_from_end(head, n):
    # Base case: if the head is None, we've reached the end of the list
    if not head:
        return None
    
    # Recursive step: move to the end of the list
    current_node = nth_node_from_end(head.next, n)
    
    # Once we reach the end of the list, start counting backwards from n
    if current_node is not None:
        return current_node
    
    count = 1
    if count == n:
        return head
    else:
        return None
    
    return current_node

The best approach for finding the nth node from the end of a linked list depends on the specific requirements of the problem. Here’s a summary comparison of the three approaches:

Approach 1: Traverse the linked list to determine its length

• Pros: Simple and straightforward, doesn’t require extra space besides a few variables
• Cons: Requires two passes through the linked list, not as efficient as other approaches

Approach 2: Use two pointers to traverse the list

• Pros: Only requires a single pass through the linked list, doesn’t modify the original list, better space complexity than approach 3
• Cons: Requires careful handling of edge cases when n is invalid

Approach 3: Recursive approach

• Pros: Doesn’t modify the original list, can be implemented recursively with fewer lines of code
• Cons: Uses a recursive function call stack that can consume a lot of memory for large lists, higher space complexity than the other two approaches

In terms of time complexity, all three approaches have a time complexity of O(n), where n is the number of nodes in the linked list.

However, approach 2 has the best space complexity, since it only requires a constant amount of extra space. Approach 3 has the highest space complexity due to the recursive function call stack.

In general, approach 2 is a good choice if we only need to find a single node from the end of the list, since it has the best time and space complexity of the three approaches and doesn’t modify the original list. What do you think?