This is one of those problems where the clean idea matters more than the amount of code. For 237. Delete Node in a Linked List, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are deleteNode.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: Time and space complexity are both O(1).
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01/**
02Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
03
04Given linked list -- head = [4,5,1,9], which looks like following:
05
06Example 1:
07
08Input: head = [4,5,1,9], node = 5
09Output: [4,1,9]
10Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
11Example 2:
12
13Input: head = [4,5,1,9], node = 1
14Output: [4,5,9]
15Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.
16
17
18Note:
19
20The linked list will have at least two elements.
21All of the nodes' values will be unique.
22The given node will not be the tail and it will always be a valid node of the linked list.
23Do not return anything from your function.
24**/
25
26//Runtime: 16 ms, faster than 51.52% of C++ online submissions for Delete Node in a Linked List.
27//Memory Usage: 9.2 MB, less than 42.02% of C++ online submissions for Delete Node in a Linked List.
28
29/**
30Approach: Swap with Next Node [Accepted]
31The usual way of deleting a node node from a linked list is to modify the next pointer of the node before it,
32to point to the node after it.
33Since we do not have access to the node before the one we want to delete,
34we cannot modify the next pointer of that node in any way. Instead, we have to replace the value of the node we want to delete with the value in the node after it, and then delete the node after it.
35
36Because we know that the node we want to delete is not the tail of the list,
37we can guarantee that this approach is possible.
38**/
39
40/**
41Complexity Analysis
42Time and space complexity are both O(1).
43**/
44
45/**
46 * Definition for singly-linked list.
47 * struct ListNode {
48 * int val;
49 * ListNode *next;
50 * ListNode(int x) : val(x), next(NULL) {}
51 * };
52 */
53class Solution {
54public:
55 void deleteNode(ListNode* node) {
56 node->val = node->next->val;
57 node->next = node->next->next;
58 }
59};Cost