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}.

 

/**
 * 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 n1 = head;
        ListNode n2 = head;
        while (n2.next != null && n2.next.next != null) {
        	n1 = n1.next;
        	n2 = n2.next.next;
        }
        n2 = n1.next;
        n1.next = null;
        ListNode right = reverse(n2);
        merge(head, right);
    }

	private void merge(ListNode head, ListNode right) {
		// TODO Auto-generated method stub
		ListNode next = null;
		while (head.next != null) {
			next = right.next;
			right.next = head.next;
			head.next = right;
			head = right.next;
			right = next;
		}
		head.next = right;
	}

	private ListNode reverse(ListNode n2) {
		// TODO Auto-generated method stub
		ListNode pre = null;
		ListNode next = null;
		while (n2 != null) {
			next = n2.next;
			n2.next = pre;
			pre = n2;
			n2 = next;
		}
		return pre;
	}
}