Logo for ammarahmed.ca
Medium
Jul 25, 2025
#linked-list

143. Reorder List

Problem

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

1L0 → L1 → … → Ln - 1 → Ln 2

Reorder the list to be on the following form:

1L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 2

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

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

Example 2:

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

Constraints:

  • The number of nodes in the list is in the range [1, 5 * 104].
    • 1 <= Node.val <= 1000

      Approach

      In order to solve this optimally, we can realize that we are essentially doing a merge on the first and second halves of the list with the second half being reversed.

      If we have, 1 -> 2 -> 3 -> 4 -> 5 -> nil, the answer is 1 -> 5 -> 2 -> 4 -> 3 -> nil. Taking the second half and reversing it, we have 5 -> 4 -> nil, with the first half being 1 -> 2 -> 3 -> nil. So, it's easy to see how merging these will give us our answer.

      In order to actually accomplish this, we have 3 steps:

      1. Find the middle
        1. Reverse the second half
          1. Merge

            Finding the middle

            To find the middle easily, we can use fast and slow pointers, when the fast pointer reaches the end, the slow pointer will be at the center.

            Reversing

            Once the middle is at found at the slow pointer, we want to reverse the list by using the slow pointers next value as our current. We'll want to separate the lists out as well by breaking the link (set slow.Next = nil)

            Merging

            To merge the lists, we create two pointers, first and second initialized to the head and reversed. We iterate while the reversed is not nil (because reversed will be the smaller list). On each iteration, we save the next values for each pointer in temporary variables (tmp1 and tmp2), we set first's next value to be second. Then, we set the second's next value to be tmp1. This is our merge step. After that we increment the pointers but settings first = tmp1 and second = tmp2.

            Complexity

            Time: O(n)

            We iterate over the list once, 3 times.

            Space: O(1)

            No extra space is created.

            Solution

            1func reorderList(head *ListNode) { 2 // Find middle of list with slow and fast pointers 3 slow, fast := head, head.Next 4 for fast != nil && fast.Next != nil { 5 slow = slow.Next 6 fast = fast.Next.Next 7 } 8 9 // Reverse the second half of the list 10 curr := slow.Next 11 slow.Next = nil 12 reversed := slow.Next 13 for curr != nil { 14 tmp := curr.Next 15 curr.Next = reversed 16 reversed = curr 17 curr = tmp 18 } 19 20 // Merge the first and second half (reversed) of the list 21 first, second := head, reversed 22 for second != nil { 23 tmp1, tmp2 := first.Next, second.Next 24 first.Next = second 25 second.Next = tmp1 26 first = tmp1 27 second = tmp2 28 } 29}