- Brute Force Solution (Count then Traverse)<\/a>
- Intuition and Approach<\/a><\/li>
- Code Implementation<\/a><\/li>
- Code Explanation<\/a><\/li>
- Dry Run<\/a><\/li>
- Time and Space Complexity<\/a><\/li>
- Conclusion<\/a><\/li><\/ul><\/li>
- Optimal Solution (Two Pointers \/ Fast and Slow)<\/a>
- Intuition and Approach<\/a><\/li>
- Code Implementation<\/a><\/li>
- Code Explanation<\/a><\/li>
- Dry Run<\/a><\/li>
- Time and Space Complexity<\/a><\/li>
- Conclusion<\/a><\/li><\/ul><\/li>
- Final Thoughts<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n
\n\n\n\nGiven the
head<\/code> of a singly linked list, return the middle node of the linked list<\/em>.<\/p>\n\n\n\nIf there are two middle nodes, return the second middle<\/strong> node.<\/p>\n\n\n\n
Example 1:<\/strong><\/p>\n\n\n\n
![\"\"\/](\"https:\/\/assets.leetcode.com\/uploads\/2021\/07\/23\/lc-midlist1.jpg\")
<\/figure>\n\n\n\nInput:<\/strong> head = [1,2,3,4,5]
Output:<\/strong> [3,4,5]
Explanation:<\/strong> The middle node of the list is node 3.<\/pre>\n\n\n\nExample 2:<\/strong><\/p>\n\n\n\n
![\"\"\/](\"https:\/\/assets.leetcode.com\/uploads\/2021\/07\/23\/lc-midlist2.jpg\")
<\/figure>\n\n\n\nInput:<\/strong> head = [1,2,3,4,5,6]
Output:<\/strong> [4,5,6]
Explanation:<\/strong> Since the list has two middle nodes with values 3 and 4, we return the second one.<\/pre>\n\n\n\nConstraints:<\/strong><\/p>\n\n\n\n
- \n
- The number of nodes in the list is in the range\u00a0
[1, 100]<\/code>.<\/li>\n\n\n\n1 <= Node.val <= 100<\/code><\/li>\n<\/ul>\n\n\n\n
\n\n\n\nBrute Force Solution (Count then Traverse)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
Let’s think about this problem step by step in the most straightforward way:<\/p>\n\n\n\n
- \n
- Why do we need to count first?<\/strong>
To find the middle of a linked list, we need to know how many nodes there are. Unlike arrays where we can directly access elements by index, linked lists require us to traverse from the beginning to reach any specific position.<\/li>\n\n\n\n- How do we find the middle position?<\/strong>
Once we know the total count\u00a0n<\/code>, the middle position is at index\u00a0n \/\/ 2<\/code>\u00a0(0-indexed). This works for both odd and even lengths:\n- \n
- For odd length (e.g., 5 nodes): middle is at index 5\/\/2 = 2 (3rd node)<\/li>\n\n\n\n
- For even length (e.g., 6 nodes): middle is at index 6\/\/2 = 3 (4th node, which is the second middle)<\/li>\n<\/ul>\n<\/li>\n\n\n\n
- Two-pass approach:<\/strong>\n
- \n
- First pass:<\/strong>\u00a0Count all nodes by traversing the entire list<\/li>\n\n\n\n
- Second pass:<\/strong>\u00a0Start from head again and move exactly\u00a0
n \/\/ 2<\/code>\u00a0steps to reach the middle<\/li>\n<\/ul>\n<\/li>\n\n\n\n- Why does this work?<\/strong>
Since we know the exact position of the middle node, we can directly navigate to it. This approach is reliable and easy to understand.<\/li>\n\n\n\n- When should you use this approach?<\/strong>
This method is great when you want to be absolutely clear about what you’re doing, or when you need to know the total length for other purposes too.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n
- Second pass:<\/strong>\u00a0Start from head again and move exactly\u00a0
- First pass:<\/strong>\u00a0Count all nodes by traversing the entire list<\/li>\n\n\n\n
- How do we find the middle position?<\/strong>
- Code Implementation<\/a><\/li>
- Code Implementation<\/a><\/li>
- Intuition and Approach<\/a><\/li>