Reorder List

Given a singly linked list L: L0?L1?…?Ln-1?Ln, reorder it to: L0?Ln?L1?Ln-1?L2?Ln-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

/**
 * 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;;
        ListNode slow = head;
        ListNode fast = head;

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

        ListNode n = reverse(slow.next);
        slow.next = null;

        ListNode m = head;

        while (m != null && n != null) {
            ListNode tempM = m.next;
            ListNode tempN = n.next;

            m.next = n;
            n.next = tempM;
            m = tempM;
            n = tempN;
        }
    }

    public ListNode reverse(ListNode start) {
        if (start == null || start.next == null) return start;

        ListNode m = start;
        ListNode n = start.next;
        start.next = null;
        while (m != null && n!= null) {
            ListNode temp = n.next;
            n.next = m;
            m =n;
            n = temp;
        }

        return m;
    }

}