/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/

class ListNode {
    int val;
    ListNode next;

    public ListNode() {}
    public ListNode(int val) { this.val = val; }
    public ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode p1 = l1, p2 = l2;
        ListNode result = new ListNode();
        ListNode rsCurr = result;

        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                rsCurr.val = p1.val;
                p1 = p1.next;
            } else {
                rsCurr.val = p2.val;
                p2 = p2.next;
            }

            rsCurr.next = new ListNode();
            rsCurr = rsCurr.next;
        }

        ListNode left = (p1 != null ? p1 : p2);

        rsCurr.val = left.val;
        rsCurr.next = left.next;
        return result;
    }

    static void dumpList(ListNode list) {
        if (list == null) {
            print("null list\n"); return;
        }

        int idx = 0;
        print("item #" + idx + ": " + list.val);

        while (list.next != null) {
            list = list.next; ++idx;
            print("item #" + idx + ": " + list.val);
        }
        print("end @@@\n");
    }

    static ListNode createNodeList(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }

        ListNode head = new ListNode(arr[0]);
        ListNode curr = head;

        for (int i = 1; i < arr.length; ++i) {
            curr.next = new ListNode(arr[i]);
            curr = curr.next;
        }

        return head;
    }

    static void print(String msg) {
        System.out.println(msg);
    }

    public static void main(String[] args) {
        int[] arr1 = {}; //{ 1, 2, 5 };
        int[] arr2 = { 1, 3, 4, 8, 9 };

        ListNode list1 = createNodeList(arr1);
        ListNode list2 = createNodeList(arr2);

        dumpList(list1); dumpList(list2);

        Solution s = new Solution();
        ListNode res = s.mergeTwoLists(list1, list2);

        print("Result: "); dumpList(res);
    }
}