LinkedList

[chipbk10]

     private ListNode middle(ListNode head) {

        ListNode dummy = new ListNode(0);
        dummy.next = head;

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

        return slow;
    }

    private ListNode reverse(ListNode head) {
        ListNode node = head, previous = null;
        while (node != null) {
            ListNode nextNode = node.next;
            node.next = previous;
            previous = node;
            node = nextNode;
        }
        return previous;
    }

    private ListNode merge(ListNode list1, ListNode list2) {
        ListNode dummyNode = new ListNode(0);        
        ListNode list3 = dummyNode;

        while (list1 != null && list2 != null) {
            ListNode next1 = list1.next;
            ListNode next2 = list2.next;

            list3.next = list1;
            list3.next.next = list2;
            list3 = list3.next.next;

            list1 = next1;
            list2 = next2;
        }                

        if (list1 != null) list3.next = list1;
        if (list2 != null) list3.next = list2;

        return dummyNode.next;
    }

    private void print(ListNode head) {
        String s = "";
        while (head != null) {
            s += " " + head.val;
            head = head.next;
        }
        System.out.println(s);
    }