LeetCode: Merge Two Sorted Lists

LeetCode: Merge Two Sorted Lists 1
\(\)

Leetcode Problem

https://leetcode.com/problems/merge-two-sorted-lists/

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

Explanation

The logic is simple, iterate both link list nodes, compare the value of nodes and add the next to result.

Use dummy node for simplifying the code, and another corner case is if a link list is longer than the other one.

Assume the length of two link list is M and N, the time complexity is \(O(Max(M, N))\).

Naive Version

CAPTURE-2019_12_24_merge-two-sorted-lists.org_20191224_154713.png

class Solution {
public:
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);
    if(l1 == NULL) return l2;
    if(l2 == NULL) return l1;

    ListNode* cur = dummy;
    while(l1 && l2) {
      if(l1->val < l2->val) {
        cur->next = l1;
        l1 = l1->next;
      } else {
        cur->next = l2;
        l2 = l2->next;
      }
      cur = cur->next;
    }

    if(l1) cur->next = l1;
    if(l2) cur->next = l2;
    return dummy->next;
  }
};

Recursive version

Another solution is using recursive iteration, the corner case is handled by the first two if test.

class Solution {
public:
  void mergeTwoLists_iter(ListNode* l1, ListNode* l2, ListNode* cur) {
    if(l1 == NULL) { cur->next = l2; return; }
    if(l2 == NULL) { cur->next = l1; return; }

    if(l1->val < l2->val) {
      cur->next = l1;
      mergeTwoLists_iter(l1->next, l2, cur->next);
    } else {
      cur->next = l2;
      mergeTwoLists_iter(l1, l2->next, cur->next);
    }
  }

  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);
    mergeTwoLists_iter(l1, l2, dummy);
    return dummy->next;
  }
};

Preparing for an interview? Check out this!

Don't miss out!
Subscribe To Newsletter

Want to be better at coding and CS ?

Programming tutorials

Career advice and tips

......

It's Free!

Invalid email address
Last Updated on

Leave a Reply

Your email address will not be published. Required fields are marked *