Delete Node at End in DSA Typescript - Time & Space Complexity

Time Complexity: Delete Node at End

O(n)

Understanding Time Complexity

We want to know how the time to delete the last node in 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.

function deleteNodeAtEnd(head: ListNode | null): ListNode | null {
  if (!head) return null;
  if (!head.next) return null;
  let current = head;
  while (current.next && current.next.next) {
    current = current.next;
  }
  current.next = null;
  return head;
}
    

This code removes the last node from a singly linked list by walking to the second last node and cutting off the last.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through the list nodes.
• How many times: It runs once for each node until the second last node.

How Execution Grows With Input

As the list gets longer, the loop runs more times, roughly one less than the number of nodes.

Input Size (n)	Approx. Operations
10	About 9 steps
100	About 99 steps
1000	About 999 steps

Pattern observation: The steps grow roughly in a straight line with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to delete the last node grows directly with the list size.

Common Mistake

[X] Wrong: "Deleting the last node is always quick because it's just one step."

[OK] Correct: You must first find the second last node by walking through the list, which takes time proportional to the list length.

Interview Connect

Understanding how operations grow with input size helps you explain your code's efficiency clearly and confidently.

Self-Check

"What if the list had a tail pointer that points directly to the last node? How would the time complexity change?"

Practice

1. What does the operation Delete Node at End do in a singly linked list?

easy

A. Adds a new node at the beginning of the list

B. Removes the first node from the list

C. Removes the last node from the list

D. Adds a new node at the end of the list

Solution

1. Step 1: Understand the operation

   Deleting a node at the end means removing the last node in the linked list.

2. Step 2: Identify the effect on the list

   After removal, the second last node becomes the new last node.

3. Final Answer:

   Removes the last node from the list -> Option C

4. Quick Check:

   Delete Node at End = Remove last node [OK]

Hint: Delete last node means remove tail node [OK]

Common Mistakes:

• Confusing delete at end with delete at start
• Thinking it adds a node instead of removing
• Assuming it deletes a middle node

2. Which of the following TypeScript code snippets correctly deletes the last node of a singly linked list named head?

easy

A. if (!head) return null;
head = head.next;

B. if (!head) return null;
let temp = head;
while (temp.next && temp.next.next) {
temp = temp.next;
}
temp.next = null;

C. let temp = head;
while (temp.next) {
temp = temp.next;
}
temp = null;

D. head = null;

Solution

1. Step 1: Analyze code for deleting last node

   if (!head) return null; let temp = head; while (temp.next && temp.next.next) { temp = temp.next; } temp.next = null; traverses to the second last node and sets its next to null, removing the last node.

2. Step 2: Check other options

   if (!head) return null; head = head.next; deletes the first node, C tries to set temp to null but does not affect list, D deletes entire list.

3. Final Answer:

   Traverse to second last node, set next to null -> Option B

4. Quick Check:

   Traverse to second last node, set next to null = A [OK]

Hint: Stop at second last node, set next to null [OK]

Common Mistakes:

• Setting temp to null does not remove node from list
• Deleting head instead of last node
• Not checking for empty or single-node list

3. Given the linked list: 1 -> 2 -> 3 -> 4 -> null, what will be the list after deleting the node at the end using this code?

function deleteAtEnd(head: Node | null): Node | null {
  if (!head) return null;
  if (!head.next) return null;
  let temp = head;
  while (temp.next && temp.next.next) {
    temp = temp.next;
  }
  temp.next = null;
  return head;
}

medium

A. 2 -> 3 -> 4 -> null

B. 1 -> 2 -> 3 -> 4 -> null

C. null

D. 1 -> 2 -> 3 -> null

Solution

1. Step 1: Understand the code logic

   The code removes the last node by stopping at second last node and setting its next to null.

2. Step 2: Apply to given list

   Original list ends with 4. After deletion, 3's next becomes null, so list is 1 -> 2 -> 3 -> null.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option D

4. Quick Check:

   Last node removed, list ends at 3 [OK]

Hint: Last node removed, second last points to null [OK]

Common Mistakes:

• Not updating second last node's next to null
• Returning null for multi-node list
• Deleting first node instead of last

4. Identify the bug in this TypeScript function that deletes the last node of a singly linked list:

function deleteAtEnd(head: Node | null): Node | null {
  if (!head) return null;
  let temp = head;
  while (temp.next) {
    temp = temp.next;
  }
  temp = null;
  return head;
}

medium

A. It does not update the second last node's next pointer

B. It does not handle empty list

C. It deletes the head node instead of last

D. It causes infinite loop

Solution

1. Step 1: Analyze the loop

   The loop moves temp to the last node, but does not track second last node.

2. Step 2: Check deletion step

   Setting temp = null only changes local variable, does not remove last node from list.

3. Final Answer:

   It does not update the second last node's next pointer -> Option A

4. Quick Check:

   Must update second last node's next to null [OK]

Hint: Update second last node's next to null, not temp variable [OK]

Common Mistakes:

• Setting temp to null does not remove node
• Not tracking second last node in loop
• Ignoring single-node list case

5. You have a singly linked list with nodes: 10 -> 20 -> 30 -> 40 -> null. Write a TypeScript function to delete the last node and return the updated list. Which of the following implementations correctly handles the edge case when the list has only one node?

hard

A. function deleteAtEnd(head: Node | null): Node | null {
if (!head) return null;
if (!head.next) return null;
let temp = head;
while (temp.next && temp.next.next) {
temp = temp.next;
}
temp.next = null;
return head;
}

B. function deleteAtEnd(head: Node | null): Node | null {
if (!head) return null;
let temp = head;
while (temp.next) {
temp = temp.next;
}
temp = null;
return head;
}

C. function deleteAtEnd(head: Node | null): Node | null {
if (!head) return null;
if (!head.next) return head;
let temp = head;
while (temp.next && temp.next.next) {
temp = temp.next;
}
temp.next = null;
return head;
}

D. function deleteAtEnd(head: Node | null): Node | null {
if (!head) return null;
if (!head.next) return head;
let temp = head;
while (temp.next) {
temp = temp.next;
}
temp.next = null;
return head;
}

Solution

1. Step 1: Check handling of single-node list

   function deleteAtEnd(head: Node | null): Node | null { if (!head) return null; if (!head.next) return null; let temp = head; while (temp.next && temp.next.next) { temp = temp.next; } temp.next = null; return head; } returns null if only one node exists, correctly deleting it.

2. Step 2: Verify deletion of last node for longer lists

   For longer lists, it traverses to the second last node using while (temp.next && temp.next.next) and sets temp.next = null, correctly removing the last node.

3. Final Answer:

   Correctly handles single-node by returning null -> Option A

4. Quick Check:

   Return null for single node, else remove last node [OK]

Hint: Return null if single node, else remove last node [OK]

Common Mistakes:

• Not returning null for single-node list
• Setting temp to null instead of updating next pointer
• Incorrect loop condition causing errors