LeetCode - Merge Two Sorted Lists

Problem description

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.

Example:

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

Analysis

Basic idea is to use another LinkedList to store the result and use two pointers to scan the two sorted list one by one.

Here’s the code:

public class MergeTwoSortedLists {
  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null){
      return l2;
    }

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

    ListNode dummy = new ListNode(0);
    ListNode p = dummy;

    while (l1 != null || l2 != null){
      if (l1 == null){
        p.next = l2;
        l2 = l2.next; // should be break; to improve efficiency
      }else if(l2 == null){
        p.next = l1;
        l1 = l1.next; // should be break; to improve efficiency
      }else {
        if (l1.val <= l2.val){
          p.next = l1;
          l1 = l1.next;
        }
        else {
          p.next = l2;
          l2 = l2.next;
        }
      }

      p = p.next;
    }

    return dummy.next;
  }
}

What to improve

• when another list is null, we can break and skip the left compare.