DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Middle of the Linked List

easyLinked list

Problem statement

You get the head of a non-empty singly linked list. Return the middle node.

If the list has an odd number of nodes there is exactly one middle. If it has an even number, there are two middle nodes; return the second one. Returning the node means the answer is the rest of the list from that node onwards.

Examples

Example 1

Input: head = 3 -> 6 -> 9 -> 12 -> 15

Output: 9 -> 12 -> 15

Explanation: Five nodes, so the third one (value 9) is the middle.

Example 2

Input: head = 10 -> 20 -> 30 -> 40

Output: 30 -> 40

Explanation: Four nodes have two middles, 20 and 30. The second one, 30, is returned.

Hints

Approach

Use slow and fast pointers.

  1. Start both at head.
  2. While fast and fast.next exist, move slow one node and fast two nodes.
  3. When the loop stops, fast has covered the whole list and slow has covered half of it, so slow is the middle.

With an even length, fast ends on null after the last node, which leaves slow on the second middle, exactly what the problem asks for. If you ever need the first middle instead, loop while fast.next and fast.next.next.

ComplexityTime O(n)Space O(1)
Python
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: ListNode | None) -> ListNode | None:
slow = fast = head
while fast and fast.next:
slow = slow.next # one step
fast = fast.next.next # two steps
return slow # fast reached the end, slow is halfway

Follow-up questions

  • Return the first middle node for even lengths instead of the second.
  • Delete the middle node and return the head of the modified list.

Frequently asked questions

Yes. It is also O(n) time and O(1) space, just with two passes instead of one. Interviewers usually accept it and then ask for the one-pass version, because the same fast and slow trick is needed in harder problems.

Finding the middle is the first step of merge sort on a linked list, of checking whether a list is a palindrome, and of reordering a list. The same two-speed pointers also detect cycles.

It is a short, clean check that you can reason about pointer movement and off-by-one boundaries, which is the kind of care needed when splitting a stream or a batch of hosts into halves for a canary rollout.