Reorder List | Leetcode

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

---

Solution:
1. Break list into two halves (use fast & slow pointers to find the middle node).
2. Reverse the second half.
3. Merge the two halves back together.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        
        // Find the middle of the list.
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        
        // Terminate the first half of the list.
        slow.next = null;
        
        // Reverse the second half of the list.
        ListNode prev = null;
        ListNode curr = mid;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        // Merge the two halves together.
        ListNode first = head;
        ListNode second = prev;
        
        while (first != null && second != null) {
            if (first != null) {
                ListNode temp = first.next;
                first.next = second;
                first = temp;
            }
            if (second != null) {
                ListNode temp = second.next;
                second.next = first;
                second = temp;
            }
        }
    }
}