Remove Nth Node from End of List in DSA Python - Time & Space Complexity

Time Complexity: Remove Nth Node from End of List

O(n)

Understanding Time Complexity

We want to understand how the time needed to remove the nth node from the end of a linked list changes as the list grows.

Specifically, how many steps does the program take when the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    fast = slow = head
    for _ in range(n):
        fast = fast.next
    if fast is None:
        return head.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return head
    

This code removes the nth node from the end of a singly linked list by using two pointers moving through the list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Moving pointers through the linked list nodes.
• How many times: The first loop moves the fast pointer n times; the second loop moves both pointers until the fast pointer reaches the end, which can be up to (length - n) times.

How Execution Grows With Input

As the list size grows, the number of steps to move pointers grows roughly in proportion to the list length.

Input Size (length)	Approx. Operations
10	About 10 steps to move pointers
100	About 100 steps to move pointers
1000	About 1000 steps to move pointers

Pattern observation: The steps increase linearly as the list size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to remove the nth node from the end grows linearly with the list size.

Common Mistake

[X] Wrong: "Since we only move the fast pointer n times first, the time complexity is O(n) where n is the given number, not the list size."

[OK] Correct: The second loop moves pointers through the rest of the list, which depends on the total list length, not just the given n. So the total steps depend on the list size.

Interview Connect

Understanding this helps you explain how to efficiently find and remove nodes from linked lists, a common task in coding challenges and real projects.

Self-Check

"What if we used a single pass with a stack instead of two pointers? How would the time complexity change?"