143. Reorder List

How to solve Reorder List (LeetCode 143): the approach in brief

The problem

You are given the head of a singly linked-list. The list can be represented as:

Pattern

Reorder List is a Linked List Manipulation Patterns problem, in the Reordering / Partitioning subpattern. The pattern covers in-place reversal, merging sorted lists, reordering, and intersection detection

Learn to reorder and partition linked lists. Master techniques like swap pairs, rotate list, and odd-even separation.

Approach outline

1. Consider how you might divide the linked list into two parts to facilitate reordering; think about finding a midpoint in the list.
2. Explore efficient ways to find the middle node of a singly linked list, such as using two pointers moving at different speeds.
3. Once you have two halves, think about reversing the second half of the list to prepare it for merging.

Complexity

The reference solution runs in O(n) time and O(n) space.

Asked at

Reorder List has been reported in interviews at Facebook, Amazon, Splunk.