leetcode ReorderList

import utils.ListNode;

public class ReorderList {
    /*
        Given a singly linked list L: L0→L1→…→Ln-1→Ln,
        reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

        You may not modify the values in the list's nodes, only nodes itself may be changed.

        Example 1:

        Given 1->2->3->4, reorder it to 1->4->2->3.
        Example 2:

        Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
     */

    public static void main(String[] args){
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        a.next = null;
//        reorderList(a);
        a.next = b;
//        reorderList(a);
//        b.next = c;
//        reorderList(a);
//        c.next = d;
        reorderList(a);
    }
    public static void reorderList(ListNode head) {
            ListNode dump = head;
            ListNode slow = head;
            ListNode fast = head;
            while(fast!=null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode mid = slow.next;
            ListNode l1 = head;
            ListNode l2 = mid;



            while(head.next != l2){
                head = head.next;
            }
            head.next = null;


            // reverse
            ListNode p = l2;
            ListNode q = p.next;
            boolean first = true;
            while(q!= null){
                ListNode t = q.next;
                q.next = p;
                if (first){
                    p.next = null;
                    first = false;
                }
                p = q;
                q = t;
            }

            l2 = p;
            p = l1;
            q = l2;

            print(l1);
            print(l2);

            // merge
            while(l2 != null){

                p = p.next;
                q = q.next;

                l1.next = l2;
                l2.next = p;

                l2 = q;
                l1 = p;

            }
            print(dump);
        }

        public static void print(ListNode head){
            ListNode t = head;
            while(t!= null){
                System.out.print(t.val+" ");
                t = t.next;
            }
            System.out.println();
        }
}