Merge Two Sorted Lists

Easy

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

Solution

Iteration

Time complexity : O(n+m)

Space complexity : O(1)

/**
* 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 dummy = new ListNode(0);
ListNode p = dummy;
while (l1 != null || l2 != null) {
if (l1 == null) {
p.next = l2;
break;
}
if (l2 == null) {
p.next = l1;
break;
}
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
return dummy.next;
}
}

LeetCode Official - Iteration

Time complexity : O(n+m)

Space complexity : O(1)

class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// maintain an unchanging reference to node ahead of the return node.
ListNode prehead = new ListNode(-1);

ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}

// exactly one of l1 and l2 can be non-null at this point, so connect
// the non-null list to the end of the merged list.
prev.next = l1 == null ? l2 : l1;

}
}

LeetCode Official - Recursion

Time complexity : O(n+m)

Space complexity : O(n+m) - The first call to mergeTwoLists does not return until the ends of both l1 and l2 have been reached, so n+m stack frames consume O(n+m) space.

class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
else if (l2 == null) {
return l1;
}
else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}

}
}

Reference

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