Let's make this one less mysterious. For 876. Middle of the Linked List, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. 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?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are middleNode.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- 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:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
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: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01/**
02Given a non-empty, singly linked list with head node head, return a middle node of linked list.
03
04If there are two middle nodes, return the second middle node.
05
06
07
08Example 1:
09
10Input: [1,2,3,4,5]
11Output: Node 3 from this list (Serialization: [3,4,5])
12The returned node has value 3. (The judge's serialization of this node is [3,4,5]).
13Note that we returned a ListNode object ans, such that:
14ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.
15Example 2:
16
17Input: [1,2,3,4,5,6]
18Output: Node 4 from this list (Serialization: [4,5,6])
19Since the list has two middle nodes with values 3 and 4, we return the second one.
20
21
22Note:
23
24The number of nodes in the given list will be between 1 and 100.
25**/
26
27//Your runtime beats 100.00 % of cpp submissions.
28/**
29 * Definition for singly-linked list.
30 * struct ListNode {
31 * int val;
32 * ListNode *next;
33 * ListNode(int x) : val(x), next(NULL) {}
34 * };
35 */
36class Solution {
37public:
38 ListNode* middleNode(ListNode* head) {
39 ListNode* step1 = head;
40 ListNode* step2 = head;
41
42 //if list has odd length, step2 will be the last node
43 //if list has even length, step2 will be NULL
44 while(step2!=NULL && step2->next!=NULL){
45 step1 = step1->next;
46 step2 = step2->next->next;
47 }
48
49 return step1;
50 }
51};
52
53/**
54Approach 1: Output to Array
55Intuition and Algorithm
56
57Put every node into an array A in order. Then the middle node is just A[A.length // 2], since we can retrieve each node by index.
58**/
59class Solution {
60public:
61 ListNode* middleNode(ListNode* head) {
62 vector<ListNode*> A = {head};
63 while (A.back()->next != NULL)
64 A.push_back(A.back()->next);
65 return A[A.size() / 2];
66 }
67};
68/**
69Complexity Analysis
70Time Complexity: O(N), where N is the number of nodes in the given list.
71Space Complexity: O(N), the space used by A.
72**/
73
74/**
75Approach 2: Fast and Slow Pointer
76Intuition and Algorithm
77
78When traversing the list with a pointer slow, make another pointer fast that traverses twice as fast.
79When fast reaches the end of the list, slow must be in the middle.
80**/
81class Solution {
82public:
83 ListNode* middleNode(ListNode* head) {
84 ListNode* slow = head;
85 ListNode* fast = head;
86 while (fast != NULL && fast->next != NULL) {
87 slow = slow->next;
88 fast = fast->next->next;
89 }
90 return slow;
91 }
92};
93/**
94Complexity Analysis
95Time Complexity: O(N), where N is the number of nodes in the given list.
96Space Complexity: O(1), the space used by slow and fast.
97**/Cost