Delete Node in a Linked List (No Head)

📋

Delete Node in a Linked List (No Head)

Edge cases:

</>

IDE

def deleteNode(node: 'ListNode') -> None:public void deleteNode(ListNode node)void deleteNode(ListNode* node)function deleteNode(node)

def deleteNode(node):
    # Write your solution here
    pass

class Solution {
    public void deleteNode(ListNode node) {
        // Write your solution here
    }
}

void deleteNode(ListNode* node) {
    // Write your solution here
}

function deleteNode(node) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: List unchanged after deletion attemptDid not copy next node's value or bypass next node; node remains unchanged.✅ Assign node.val = node.next.val and node.next = node.next.next to delete node.

Wrong: List broken or tail node lostIncorrect pointer manipulation causing list disconnection or tail removal.✅ Ensure node.next points to node.next.next after copying value; do not remove tail node.

Wrong: TLE or timeout on large inputTraversal from head to node causing O(n) time complexity.✅ Delete node in O(1) by copying next node's value and bypassing next node without traversal.

Wrong: Deleted wrong node or off-by-one errorIncorrect node identification or pointer usage.✅ Confirm node to delete is correct and copy next node's value into it before bypassing.

Wrong: Attempted to delete node by reassigning head pointerMisunderstanding that head pointer is not accessible.✅ Delete node by copying next node's value and bypassing next node; do not reassign head.

✓

Test Cases

Focus on handling minimal and boundary cases correctly.

Be aware of common pitfalls like greedy deletion and off-by-one errors.

Optimize your solution to run in constant time without traversal.

t1_01basic

Input{"list":[4,5,1,9],"node_to_delete_index":1}

Expected[4,1,9]

⏱ Performance - must finish in 2000ms

We copy the value from the next node (1) into the node to delete (5), then bypass the next node.

💡 Think about how to remove a node without access to the head of the list.

💡 Use the technique of copying the next node's value into the current node and bypassing the next node.

💡 Set node.val = node.next.val and node.next = node.next.next to delete the node.

Why it failed: Failed to delete node correctly: likely did not copy next node's value or bypass next node. Fix by assigning node.val = node.next.val and node.next = node.next.next.

✓ Correctly deleted the node by copying next node's value and bypassing it.

t1_02basic

Input{"list":[1,2,3,4],"node_to_delete_index":2}

Expected[1,2,4]

⏱ Performance - must finish in 2000ms

Deleting node with value 3 by copying next node's value (4) and bypassing next node.

💡 Remember you cannot delete the tail node, so node.next is always valid.

💡 Copy the next node's value into the current node and link current node to next node's next.

💡 Use node.val = node.next.val and node.next = node.next.next to remove the node.

Why it failed: Incorrect deletion: possibly tried to remove node by changing pointers without copying value. Fix by copying next node's value and bypassing next node.

✓ Node deleted correctly using the copy and bypass method.

t2_01edge

Input{"list":[10,20],"node_to_delete_index":0}

Expected[20]

⏱ Performance - must finish in 2000ms

Deleting the first node (index 0) in a 2-node list reduces list to single node.

💡 Test the minimal list size allowed (2 nodes).

💡 Ensure deletion works when node to delete is the first node accessible.

💡 Copy next node's value and bypass next node to reduce list size correctly.

Why it failed: Failed on minimal list size: did not handle deletion when list has only two nodes. Fix by copying next node's value and bypassing next node.

✓ Correctly handled deletion in minimal 2-node list.

t2_02edge

Input{"list":[7,8,9],"node_to_delete_index":1}

Expected[7,9]

⏱ Performance - must finish in 2000ms

Deleting middle node (index 1) keeps list connected and tail intact.

💡 Check deletion of a node in the middle of the list.

💡 Verify that the list remains connected after deletion.

💡 Copy next node's value and bypass next node to maintain list integrity.

Why it failed: Middle node deletion failed: list became disconnected or tail lost. Fix by copying next node's value and bypassing next node.

✓ Middle node deleted correctly with list connectivity preserved.

t2_03edge

Input{"list":[3,4,5,6],"node_to_delete_index":2}

Expected[3,4,6]

⏱ Performance - must finish in 2000ms

Deleting node just before tail (index 2) keeps tail node intact.

💡 Test deletion of node just before the tail node.

💡 Ensure tail node remains unchanged after deletion.

💡 Copy next node's value and bypass next node to delete correctly.

Why it failed: Failed to preserve tail node when deleting node before tail. Fix by copying next node's value and bypassing next node.

✓ Node before tail deleted correctly with tail preserved.

t2_04edge

Input{"list":[100,200,300],"node_to_delete_index":0}

Expected[200,300]

⏱ Performance - must finish in 2000ms

Deleting the first accessible node in a 3-node list updates list correctly.

💡 Deleting the first node requires copying next node's value.

💡 Ensure you do not lose the rest of the list after deletion.

💡 Copy next node's value and bypass next node to maintain list.

Why it failed: Failed to delete first accessible node properly; list may be broken. Fix by copying next node's value and bypassing next node.

✓ First accessible node deleted correctly with list intact.

t3_01corner

Input{"list":[1,2,3,4,5],"node_to_delete_index":3}

Expected[1,2,3,5]

⏱ Performance - must finish in 2000ms

Greedy trap: trying to delete node by just nullifying it without copying next node's value fails.

💡 Beware of trying to delete node by setting node = null or node.next = null.

💡 Remember you must copy next node's value and bypass next node.

💡 Fix by assigning node.val = node.next.val and node.next = node.next.next.

Why it failed: Greedy trap: deleting node by nullifying it breaks list. Fix by copying next node's value and bypassing next node. This is the greedy trap test.

✓ Correctly avoided greedy trap by copying next node's value and bypassing it.

t3_02corner

Input{"list":[10,20,30,40],"node_to_delete_index":1}

Expected[10,30,40]

⏱ Performance - must finish in 2000ms

Off-by-one error: deleting wrong node due to incorrect indexing or pointer usage.

💡 Check that you are deleting the correct node, not the next or previous one.

💡 Verify that node_to_delete_index matches the node passed to function.

💡 Ensure you copy next node's value into the correct node and bypass next node.

Why it failed: Off-by-one error: deleted wrong node or list corrupted. Fix by correctly identifying node to delete and copying next node's value into it.

✓ Correct node deleted with no off-by-one errors.

t3_03corner

Input{"list":[5,6,7,8,9],"node_to_delete_index":0}

Expected[6,7,8,9]

⏱ Performance - must finish in 2000ms

Confusing 0/1 deletion: must not try to delete head by reassigning head pointer (not accessible).

💡 You do not have access to head, so cannot reassign it.

💡 Delete node by copying next node's value and bypassing next node.

💡 Fix by node.val = node.next.val and node.next = node.next.next.

Why it failed: Tried to delete node by reassigning head pointer which is not accessible. Fix by copying next node's value and bypassing next node. This is the 0/1 deletion confusion test.

✓ Deleted node correctly without needing head pointer.

t4_01performance

Input{"list":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"node_to_delete_index":50}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 nodes; solution must run in O(1) time to avoid TLE.

💡 Brute force traversal from head to node is O(n) and may time out.

💡 Optimal solution copies next node's value and bypasses next node in O(1) time.

💡 Implement in-place deletion without traversal to pass performance test.

Why it failed: TLE due to O(n) traversal from head to node. Fix by deleting node in O(1) by copying next node's value and bypassing next node.

✓ Solution runs in O(1) time confirming optimal complexity.

Practice

1. 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

2. You are given a singly linked list with unsorted integer values. You need to sort the list in ascending order with O(n log n) time complexity and O(1) auxiliary space. Which algorithmic approach best fits this requirement?

easy

A. Perform a bottom-up iterative merge sort directly on the linked list without extra arrays.

B. Use a recursive quicksort on the linked list by partitioning around a pivot node.

C. Extract all values into an array, sort the array using quicksort, then rebuild the linked list.

D. Apply a greedy insertion sort by inserting nodes into a new sorted list one by one.

Solution

1. Step 1: Understand time and space constraints

   The problem requires O(n log n) time and O(1) auxiliary space, which rules out array extraction and recursive approaches that use extra space.

2. Step 2: Identify algorithm matching constraints

   Bottom-up iterative merge sort on linked lists achieves O(n log n) time and O(1) space by merging sublists iteratively without recursion or extra arrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bottom-up merge sort is the standard in-place linked list sorting method [OK]

Hint: Bottom-up merge sort is in-place and O(n log n) [OK]

Common Mistakes:

• Thinking quicksort is efficient on linked lists due to lack of random access
• Assuming insertion sort is efficient for large lists
• Believing array extraction is O(1) space

3. What is the time and space complexity of the optimal in-place iterative merge algorithm for merging two sorted linked lists of lengths n and m?

medium

A. Time: O(max(n, m)), Space: O(1)

B. Time: O(n·m), Space: O(1)

C. Time: O(n + m), Space: O(n + m)

D. Time: O(n + m), Space: O(1)

Solution

1. Step 1: Analyze time complexity

   The algorithm traverses each node exactly once, either from l1 or l2, so total steps are proportional to n + m.

2. Step 2: Analyze space complexity

   It rearranges pointers in-place without allocating new nodes or recursion stack, so auxiliary space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space for in-place merge [OK]

Hint: In-place merge visits each node once, no extra space [OK]

Common Mistakes:

• Confusing time as O(n·m) due to nested loops
• Assuming recursion adds O(n + m) stack space
• Thinking space is O(n + m) due to new list creation

4. What is the space complexity of the recursive approach to remove duplicates from a sorted linked list, and why might a common alternative answer be incorrect?

medium

A. O(1) because no extra data structures are used.

B. O(n) because a hash set is used to track duplicates.

C. O(log n) because the recursion depth is halved each call.

D. O(n) due to recursion stack space in the worst case.

Solution

1. Step 1: Identify recursion depth

   In the worst case, recursion proceeds one node at a time, leading to O(n) recursive calls on the stack.

2. Step 2: Analyze space usage

   No auxiliary data structures like hash sets are used, so extra space is only recursion stack space, which is O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursive calls stack up to list length [OK]

Hint: Recursion stack space counts as extra space [OK]

Common Mistakes:

• Assuming O(1) space since no explicit data structures
• Confusing recursion depth with log n
• Thinking hash sets are used

5. Suppose you want to merge k sorted linked lists but now the lists can contain duplicate values and you want to return only the top M smallest unique values in sorted order. Which modification to the min-heap approach correctly achieves this?

hard

A. Use a min-heap and maintain a hash set to skip duplicates when extracting nodes, stopping after M unique values.

B. Use the same min-heap approach but stop after extracting M nodes, ignoring duplicates.

C. Merge all lists into one array, remove duplicates, sort, and return first M values.

D. Sequentially merge lists and remove duplicates during merge until M unique values are collected.

Solution

1. Step 1: Understand requirement for unique values

   Duplicates must be skipped, and only M unique smallest values returned.

2. Step 2: Modify min-heap approach

   Maintain a hash set to track seen values; when popping from heap, skip if duplicate; stop after M unique values.

3. Step 3: Why other options fail

   Stopping after M nodes ignores duplicates; merging all nodes wastes time and space; sequential merges are inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash set + min-heap ensures unique sorted extraction efficiently [OK]

Hint: Use hash set with min-heap to filter duplicates on the fly [OK]

Common Mistakes:

• Stopping after M nodes without filtering duplicates
• Sorting all nodes wastes time
• Sequential merges inefficient for large k