EasyLinked ListTwo Pointers

Middle of the Linked List

1 approach, code in every language

You are given the head of a singly linked list. Your job is to find and return the middle node of that list.

When the list contains an odd number of nodes there is a single, unambiguous middle. When the number of nodes is even there are two nodes in the center, and in that case you should return the second of the two.

Example 1

Input: head = [1,2,3,4,5]

Output: [3,4,5]

The list has five nodes, so the middle is the node with value 3.

Example 2

Input: head = [1,2,3,4,5,6]

Output: [4,5,6]

With six nodes the two central values are 3 and 4; we return the second one, the node with value 4.

Constraints

The number of nodes is in the range [1, 100].
1 <= Node.val <= 100

Fast and Slow Pointers

Advance one pointer twice as fast so it lands on the middle in a single pass.

Loading animation…

Intuition

If one pointer moves a single step at a time while another moves two steps at a time, the faster one reaches the end exactly when the slower one reaches the center. This works because after k iterations the slow pointer has traveled k nodes and the fast pointer has traveled 2k nodes. The moment the fast pointer runs out of room (it becomes null or its next is null), the slow pointer is sitting on the middle. Starting both at the head naturally returns the second middle for even-length lists, which is exactly what we want. It needs only one traversal and a couple of pointers.

Algorithm walkthrough

1Initialize both slow and fast to point at the head of the list.
2Loop while fast is not null and fast.next is not null.
3On each iteration, move slow forward by one node and fast forward by two nodes.
4When the loop condition fails, fast has passed the end and slow has reached the middle.
5Return slow, which for even lengths is the second of the two middle nodes.

Implementation

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

Time

O(n)

Space

O(1)

One traversal of the list using only two pointers.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Pump Chain Midpoint is our own problem on the technique behind Middle of the Linked List: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free