Tue 08 Jan 2019

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.

It’s an easy problem in Leetcode for practicing linked list. It’s similar to the merge step of the Merge sort.

Brute force algorithm

Merge the both list together and sort the returning list. This will take complexitiy of @L O(n + m)log(n + m) @L , where n & m are length of each two list.

More efficient solution

Similary to algorithm used in merging step of Merge Sort, we can acheive @L O(n + m) @L time complexity. Traverse both the list together, and insert the smallest value into the new list.

public class ListNode {
   int val;
   ListNode next;
   ListNode(int x) { val = x; }
}

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode l3 = null;
        ListNode tail = null;

        while (l1 != null && l2 != null) {
            int lowestValue;

            if (l1.val < l2.val) {
                lowestValue = l1.val;
                l1 = l1.next;
            } else {
                lowestValue = l2.val;
                l2 = l2.next;
            }

            if (l3 == null) {
                l3 = new ListNode(lowestValue);
                tail = l3;
            } else {
                ListNode ptr = new ListNode(lowestValue);
                tail.next = ptr;
                tail = ptr;
            }
        }

        //if any of the two lists is not yet completely traversed
        if (tail != null) {
            tail.next = l1 != null ? l1 : l2;
        } else {
            l3 = l1 != null ? l1 : l2;
        }

        return l3;
    }
}

Footnotes

Leetcode
↩