Merge Two Sorted Lists

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

Examples:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Approach 1:

Let’s begin with the most straight forward solution. Often the power lies in an incremental solution. Start with the most naive approach and proceed to evaluating and improving the code in small steps.

//Approach 1:
//RunTime: 6ms
//Memory usage: 41.3MB
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode output=null;
    if((l1!=null && l2!=null && l1.val<=l2.val) || (l1!=null && l2==null)) {
     output = new ListNode(l1.val);
              l1 = l1.next;
    } else if(l2!=null){
     output = new ListNode(l2.val);
              l2 = l2.next;
    }
        ListNode previousNode = output;
   while(l1!=null || l2!=null) {
    if((l1!=null && l2!=null && l1.val<=l2.val) || (l1!=null && l2==null)) {
      previousNode.next = new ListNode(l1.val);
      l1 = l1.next;
     } else {
      previousNode.next = new ListNode(l2.val);  
      l2 = l2.next;
     }
    previousNode = previousNode.next;
        }
   return output;
    }
}

Well, clearly, I have a long way to go in improving this solution. Mat be you would want to have a look at this.

Find more posts here.

Cheers & Chao!