Interview Question Merge Two Sorted Lists

By Fatih KABAKCI

The problem is to merge two sorted list into a new list.

Problem #21 - Merge Two Sorted Lists

Description: 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.

Difficulty: Easy

Solution in Java

package com.fatihkabakci.Easy.MergeTwoSortedLists;

/**
 * @author fkabakci
 * 
 * Problem Description: 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.
 * 
 * Solution:
 * 1. Start with the first elements. See that which one is lower than the another one, 
 * 	  then put that one (minimum one) into the list.
 * 2. Pass to the next one in the list which had a minimum one previous.
 */
public class MergeTwoSortedLists {	
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode head = new ListNode(0);
        ListNode l3 = head;
        while(l1 != null || l2 != null) {
        	int val1 = (l1 != null) ? l1.val : Integer.MAX_VALUE;
        	int val2 = (l2 != null) ? l2.val : Integer.MAX_VALUE;
        	l3.next = new ListNode(Math.min(val1, val2));
    		l3 = l3.next;
        	if(val1 < val2) 
        		l1 = l1.next;
        	else
        		l2 = l2.next;
        }
        return head.next;
    }
	
	public static void main(String[] args) {
		MergeTwoSortedLists r = new MergeTwoSortedLists();
		ListNode head = Data.init(new int[]{1, 2, 3});
		ListNode tail = Data.init(new int[]{4, 5, 6});
		ListNode entire = r.mergeTwoLists(head, tail);
		while(entire != null) {
			System.out.print(entire.val + " ->");
			entire = entire.next;
		}
	}
}