mergeTwoLists.java

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

public class HelloWorld {
    public static void printList(ListNode node) {
        while (node != null) {
            System.out.print(" -> " + node.val);
            node = node.next;
        }
    }

    public static ListNode convertToNode(int[] arr) {

        ListNode head = null, node = null;

        for(int i: arr) {
            if(node == null) {
                node = new ListNode(i);
                head = node;
            }
            else {
                node.next = new ListNode(i);
                node = node.next;
            }
        }

        return head;
    }

    public static void main(String [] args) {
        int[] arrayOne = { 1, 3, 5, 7, 9, 11 };
        int[] arrayTwo = { 2, 4, 6, 8, 10 };

        ListNode listOne = convertToNode(arrayOne);
        ListNode listTwo = convertToNode(arrayTwo);

        ListNode resultList = mergeTwoLists(listOne, listTwo);

        printList(resultList);
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if(list1 == null) {
            return list2;
        }

        if(list2 == null) {
            return list1;
        }

        ListNode head;

        if(list1.val < list2.val) {
            head = list1;
            head.next = mergeTwoLists(list1.next, list2);
        }
        else {
            head = list2;
            head.next = mergeTwoLists(list1, list2.next);
        }

        return head;
    }
}