Delete Node in a Linked List (No Head)

▶

Steps

setup

Setup: Initial Linked List and Node to Delete

We start with the linked list 4 -> 5 -> 1 -> 9. The node to delete is the one with value 5, which is the second node.

💡 Understanding the initial structure and which node is targeted is essential before any changes happen.

Line:

n4 = ListNode(9)
n3 = ListNode(1, n4)
n2 = ListNode(5, n3)
n1 = ListNode(4, n2)

💡 The node to delete is not the tail, so the algorithm will copy values from next nodes.

compare

Check if node.next.next is None (Is next node the tail?)

We check if the node after the node to delete is the tail by verifying if node.next.next is None. Here, node.next is 1, and node.next.next is 9, which is not None.

💡 This check determines if we are at the second last node, which changes how deletion proceeds.

Line:

if node.next.next is None:

💡 Since the next node is not the tail, we must recurse deeper.

traverse

Recursive call: deleteNode(node.next)

Since the next node is not the tail, we recursively call deleteNode on node.next, which is the node with value 1.

💡 Recursion moves the deletion process forward until the second last node is reached.

Line:

deleteNode(node.next)

💡 The algorithm defers deletion until it reaches the node before the tail.

compare

Check if node.next.next is None at node with value 1

At node with value 1, check if node.next.next is None. node.next is 9, and node.next.next is None, so this condition is true.

💡 This identifies that the current node is the second last node, so deletion can proceed here.

Line:

if node.next.next is None:

💡 We have reached the node before the tail, so we can copy the tail's value and remove it.

insert

Copy tail node's value into current node

We copy the value from the tail node (9) into the current node (1), effectively overwriting 1 with 9.

💡 Copying the tail's value into the second last node prepares to remove the tail node.

Line:

node.val = node.next.val

💡 This step shifts the tail's value backward, preserving list integrity after deletion.

delete

Remove tail node by setting next to None

We remove the tail node by setting the current node's next pointer to None, detaching the old tail.

💡 Removing the tail node finalizes the deletion process.

Line:

node.next = None

💡 This detaches the last node, effectively shortening the list by one.

traverse

Return from recursion to previous node (value 5)

We return from the recursive call to the previous node (value 5) to continue updating values.

💡 Returning allows the algorithm to propagate value changes backward.

Line:

deleteNode(node.next)

💡 The recursion unwinds, enabling value copying back up the list.

insert

Copy next node's value into current node (5 becomes 9)

We copy the value from the next node (9) into the current node (5), overwriting 5 with 9.

💡 This shifts the values backward, effectively removing the original node to delete's value.

Line:

node.val = node.next.val

💡 Value copying replaces the deleted node's value with the next node's value.

traverse

Return from recursion to original call (node with value 4)

We return from the recursive call to the original call at the head node (value 4).

💡 The recursion fully unwinds, and the list is now updated.

Line:

deleteNode(node.next)

💡 All necessary value shifts and deletions are complete.

traverse

Traverse and print final linked list

We traverse the updated linked list starting from head to read the final values: 4 -> 9 -> 9.

💡 Reading the list confirms the deletion effect.

Line:

curr = n1
while curr:
    print(curr.val, end=' -> ' if curr.next else '\n')
    curr = curr.next

💡 The final list shows the node with value 5 replaced by 9, but the last node is still 9, indicating a duplicate tail node remains.

prune

Correct final linked list by removing duplicate tail node

We finalize the deletion by removing the duplicate tail node, setting the next pointer of the second node to null, resulting in 4 -> 9.

💡 This step ensures the list ends correctly without duplicate values.

Line:

node.next = None  # Remove duplicate tail node

💡 Removing the duplicate tail node maintains list integrity and reflects the correct deletion.

reconstruct

Final linked list after deletion

The final linked list is 4 -> 9 after deleting the node with value 5 by copying values and removing the tail node.

💡 This confirms the algorithm's correctness and the list's integrity after deletion.

Line:

N/A - final state

💡 The node with value 5 is effectively removed by value copying and pointer adjustment.

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

def deleteNode(node):
    # STEP 2: Check if next node is tail
    if node.next.next is None:
        # STEP 5: Copy tail value
        node.val = node.next.val
        # STEP 6: Remove tail
        node.next = None
        return
    # STEP 3: Recurse deeper
    deleteNode(node.next)
    # STEP 8: Copy next node's value back
    node.val = node.next.val

# Driver code
if __name__ == '__main__':
    n4 = ListNode(9)  # STEP 1
    n3 = ListNode(1, n4)
    n2 = ListNode(5, n3)
    n1 = ListNode(4, n2)

    deleteNode(n2)  # STEP 3

    curr = n1  # STEP 10
    while curr:
        print(curr.val, end=' -> ' if curr.next else '\n')
        curr = curr.next

📊

Delete Node in a Linked List (No Head) - Watch the Algorithm Execute, Step by Step

Watching each pointer and value change live helps you understand how in-place deletion works without needing the head pointer.

setup

4

→

5

→

1

→

9

compare

4

→

5

→

1

→

9

traverse

4

→

5

→

1

→

9

compare

4

→

5

→

1

→

9

insert

4

→

5

→

9

→

9

detach

4

→

5

→

9

traverse

4

→

5

→

9

insert

4

→

9

→

9

traverse

4

→

9

→

9

Visualization loading…

prune

4

→

9

Result: [4, 9]

reconstruct

4

→

9

Result: [4, 9]

Key Takeaways

✓ In-place deletion without head pointer is done by copying the next node's value and bypassing the next node.

This insight is hard to see from code alone because it relies on understanding pointer manipulation and value shifting.

✓ The recursion unwinds from the second last node, enabling value copying backward to the node to delete.

Visualizing recursion helps understand how the algorithm propagates changes up the list.

✓ The last node is removed by setting the next pointer of the second last node to null, shortening the list.

This step is critical to avoid duplicate tail nodes and maintain list integrity.

Practice

1. Given two singly linked lists that may or may not intersect, which approach guarantees finding the intersection node in O(m + n) time and O(1) space without modifying the lists?

easy

A. Store all nodes of the first list in a hash set, then check each node of the second list against the set.

B. Use nested loops to compare every node in the first list with every node in the second list.

C. Use two pointers starting at each list head, switching heads when reaching the end, to equalize path lengths and find the intersection.

D. Sort both lists by node values and then scan simultaneously to find matching values.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the intersection node without extra space and in linear time.

2. Step 2: Evaluate approaches

   Nested loops (B) are O(m*n), hash set (C) uses extra space, sorting (D) is invalid as node values may not be unique and sorting modifies lists. The two-pointer approach (A) equalizes path lengths by switching heads, ensuring both pointers traverse equal total lengths and meet at the intersection or end.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer approach is O(m+n) time and O(1) space [OK]

Hint: Two pointers switching heads equalize lengths [OK]

Common Mistakes:

• Confusing node values with node references
• Using extra space unnecessarily
• Assuming sorting helps with intersection

2. You are given two singly linked lists, each sorted in ascending order. You need to merge them into a single sorted linked list without using extra space for new nodes. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Iteratively merge the two lists in-place by rearranging pointers without extra nodes.

B. Sort both lists independently using merge sort, then concatenate them.

C. Use a greedy approach that picks the smallest node from either list and appends it to a new list.

D. Use a recursive merge that creates new nodes for the merged list.

Solution

1. Step 1: Understand the problem constraints

   The problem requires merging two sorted linked lists into one sorted list without allocating new nodes, so extra space usage must be O(1).

2. Step 2: Identify the approach that rearranges pointers in-place

   Iterative in-place merging rearranges the next pointers of existing nodes, achieving O(n + m) time and O(1) space, which is optimal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   In-place iterative merge uses constant extra space and linear time [OK]

Hint: In-place iterative merge uses O(1) space and linear time [OK]

Common Mistakes:

• Assuming recursion is always optimal despite stack space
• Thinking greedy append to new list is in-place
• Sorting lists separately then concatenating is inefficient

3. Consider the following Python code for merging two sorted linked lists in-place:

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

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val > l2.val:
        l1, l2 = l2, l1
    head = l1
    while l1 and l2:
        prev = None
        while l1 and l1.val <= l2.val:
            prev = l1
            l1 = l1.next
        prev.next = l2
        l1, l2 = l2, l1
    return head

# Input lists:
# l1: 1 -> 3 -> 5
# l2: 2 -> 4

merged_head = mergeTwoLists(l1, l2)

What is the value of the node pointed to by prev after the first inner while loop iteration inside the outer while loop?

easy

A. Node with value 3

B. Node with value 5

C. Node with value 1

D. Node with value 2

Solution

1. Step 1: Trace the inner while loop with initial lists

   Initially, l1 points to 1, l2 points to 2. The inner loop advances l1 while l1.val <= l2.val: - l1=1 (<=2), prev=1, l1 moves to 3 - l1=3 (>2), loop stops

2. Step 2: Identify prev after loop

   Prev points to node with value 1 after the inner loop ends, which is the last node with value less than or equal to l2.val.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Prev points to last l1 node ≤ current l2 node [OK]

Hint: Prev points to last l1 node ≤ current l2 node [OK]

Common Mistakes:

• Assuming prev points to node with value 3 after first inner loop
• Confusing l1 and l2 pointers after swap
• Forgetting that prev updates inside inner loop

4. Suppose the linked lists can contain cycles (loops). Which modification to the two-pointer approach is necessary to correctly find the intersection node or determine no intersection?

hard

A. Convert lists to arrays and use hash sets to detect intersection nodes.

B. Use the original two-pointer approach without changes; it will detect intersection even with cycles.

C. Modify the two-pointer approach to limit iterations to m + n to avoid infinite loops.

D. Run Floyd's cycle detection on both lists first; if cycles exist, find cycle entry points and check if they intersect.

Solution

1. Step 1: Understand impact of cycles

   Cycles cause infinite loops in the original two-pointer approach, making it unreliable.

2. Step 2: Detect and handle cycles

   Use Floyd's cycle detection to find cycles and their entry points. If both lists have cycles, check if cycles intersect by comparing cycle entry nodes.

3. Step 3: Decide intersection

   If cycles intersect, return intersection node; else, no intersection.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Cycle detection prevents infinite loops and correctly finds intersection [OK]

Hint: Detect cycles first to avoid infinite loops [OK]

Common Mistakes:

• Assuming no cycles exist
• Not limiting iterations causing infinite loops
• Ignoring cycle entry points for intersection

5. Suppose you want to modify the bottom-up merge sort on a linked list to handle the case where the list nodes can be reused multiple times (i.e., duplicates allowed and nodes can appear multiple times). Which modification is necessary to maintain correctness and efficiency?

hard

A. Add a hash set to track visited nodes during merge to prevent infinite loops caused by reuse.

B. No modification needed; the existing algorithm handles duplicates and reuse naturally.

C. Modify the merge function to create new nodes instead of reusing existing nodes to avoid cycles.

D. Switch to recursive merge sort to better handle node reuse and duplicates.

Solution

1. Step 1: Understand node reuse implications

   If nodes can be reused multiple times, re-linking existing nodes in merge can create cycles or corrupt list structure.

2. Step 2: Modify merge to create new nodes

   Creating new nodes during merge avoids modifying shared nodes, preventing cycles and preserving correctness.

3. Step 3: Evaluate other options

   Tracking visited nodes adds overhead and complexity; recursion does not solve reuse issues; no modification risks infinite loops.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Creating new nodes ensures safe merges with reused nodes [OK]

Hint: Reusing nodes requires copying to avoid cycles [OK]

Common Mistakes:

• Assuming existing merge works with reused nodes
• Trying to detect cycles dynamically instead of preventing
• Switching to recursion without addressing reuse