MergeTwoSortedList.java

package linked_list;

/**
 * Created by gouthamvidyapradhan on 18/03/2017.
 * Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
 */
public class MergeTwoSortedList {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static void main(String[] args) throws Exception {
        ListNode head = new ListNode(0);
        ListNode head1 = new ListNode(3);
        ListNode head2 = new ListNode(8);

        ListNode head3 = new ListNode(1);
        ListNode head4 = new ListNode(2);
        ListNode head5 = new ListNode(7);
        ListNode head6 = new ListNode(10);

        head.next = head1;
        head1.next = head2;

        head3.next = head4;
        head4.next = head5;
        head5.next = head6;

        ListNode newHead = new MergeTwoSortedList().mergeTwoLists(head, head3);
        ListNode link = newHead;
        while (link != null) {
            System.out.println(link.val);
            link = link.next;
        }
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        else if (l2 == null) return l1;
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}