Remove Nth Node from End of List in DSA C - 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.

How does the number of steps grow when the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode *fast = head, *slow = head;
    for (int i = 0; i < n; i++)
        fast = fast->next;
    if (!fast) 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 using two pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two loops: one moves the fast pointer n steps, the other moves both pointers until fast reaches the end.
• How many times: The first loop runs n times; the second loop runs (length - n) times, where length is the total nodes in the list.

How Execution Grows With Input

As the list length grows, the total steps grow roughly in a straight line with the list size.

Input Size (length)	Approx. Operations
10	About 10 steps to move fast + up to 9 steps to move slow and fast = ~19 steps
100	About 100 steps total
1000	About 1000 steps total

Pattern observation: The number of steps grows roughly in direct proportion to the list size.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Because we only move the fast pointer n steps first, the time complexity is O(n) where n is the position from the end, not the list length."

[OK] Correct: The second loop moves through the rest of the list, which depends on the total list length, so the overall time depends on the full list size, not just n.

Interview Connect

Understanding this linear time approach shows you can efficiently handle linked list problems without extra space, a skill often valued in coding challenges.

Self-Check

"What if we used a single pass approach without two pointers? How would the time complexity change?"