/**
 * 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 one = head;
    ListNode mid = midNode(head);
    ListNode two = mid.next;
    mid.next = null;
    two = reverse(two);

    ListNode curr = one;
    while (one != null && two != null) {
      one = one.next;
      curr.next = two;
      two = two.next;
      curr.next.next = one;
      curr = curr.next.next;
    }
    if (two == null) {
      two = one;
    }
    return head;
  }

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

  public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    ListNode newHead = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
  }
}