/**
 * class ListNode {
 *   public int value;
 *   public ListNode next;
 *   public ListNode(int value) {
 *     this.value = value;
 *     next = null;
 *   }
 * }
 */
public class Solution {
  public ListNode reorder(ListNode head) {
    // Write your solution here.
    if (head == null || head.next == null) {
      return head;
    }
    ListNode middle = findMiddle(head);
    ListNode one = head;
    ListNode two = middle.next;
    middle.next = null;
    ListNode reversedList = reverse(two);

    return connectTwoLinkedLists(one, reversedList);
  }

  private ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head.next;

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

    return slow;
  }

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

  private ListNode connectTwoLinkedLists(ListNode one, ListNode two) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while(one != null && two != null) {
      cur.next = one;
      one = one.next;
      cur.next.next = two;
      two = two.next;
      cur = cur.next.next;
    }
    if (one != null) {
      cur.next = one;
    }
    if (two != null) {
      cur.next = two;
    }
    return dummy.next;
  }
}

三个链表的基本操作： 找中点，翻转链表， 链接链表。 注意的点是找到中点后，分开两部分链表，记得要断开中点的连接点。