public ListNode reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode middle = findMiddle(head);
        ListNode l2 = middle.next;
        middle.next = null;
        
        // reverse the second half
        l2 = reverseList(l2);
        
        // merge two lists
        ListNode l1 = head;
        ListNode tail = head;
        while (l1 != null && l2 != null) {
            ListNode tmp1 = l1.next;
            ListNode tmp2 = l2.next;
            tail.next = l1;
            l1.next = l2;
            tail = l2;
            
            l1 = tmp1;
            l2 = tmp2;
        }
        if (l1 != null) {
            tail.next = l1;
        }
        return head;
        
    }