Where it runs
1. The problem
Where is the middle node of a linked list? In an array you would take length / 2 and read the item at that index right away. A linked list stores no length, and you can't jump by index. The simple way: walk the whole list and count the nodes, then walk again up to the half. That is two passes.
There is a way to do it in one pass. It uses the most useful method for linked lists: two pointers that move at different speeds. The same method finds a loop in a list, finds the n-th node from the end, and splits a list in half for merge sort.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems that need the middle of a linked list, or the two halves it splits into, without counting the length first. Move slow one node and fast two, and slow stops on the middle.
This is the lesson task, returning the second middle on an even length.
Stop slow one node before the middle, then unlink the middle.
Find the middle, reverse the second half as in lesson 46, then add up the pairs.
Find the middle, reverse the back half, and compare it with the front.