Reorder List

Why it belongs on this sheet

This is a strong medium because it combines multiple linked-list building blocks into one coherent solution.

Pattern

Find middle, reverse second half, weave

Approach

Split the list into two halves, reverse the second half, then merge nodes alternately from the first and reversed second half.

Java solution

class Solution {
  public void reorderList(ListNode head) {
    if (head == null || head.next == null) {
      return;
    }

    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }

    ListNode second = reverse(slow.next);
    slow.next = null;
    ListNode first = head;

    while (second != null) {
      ListNode nextFirst = first.next;
      ListNode nextSecond = second.next;
      first.next = second;
      second.next = nextFirst;
      first = nextFirst;
      second = nextSecond;
    }
  }

  private ListNode reverse(ListNode head) {
    ListNode previous = null;
    while (head != null) {
      ListNode next = head.next;
      head.next = previous;
      previous = head;
      head = next;
    }
    return previous;
  }
}

Complexity

• Time: O(n)
• Space: O(1)

Interview note

Breaking it into three named steps makes the explanation much easier to follow.