Solution by akshaynagpal

• Approach #1 Iterative Method [Accepted]

Intuition

Keep comparing the list nodes at each step and increment the node pointer that is smaller.
For example let the given lists be:
`l1`: `1->3->8->9` and `l2`: `2->5->7`.
Since we are merging the sorted lists in ascending order we need to start with finding the smaller node. The smaller node is `1` out of both the lists. Hence we have the `head` as `1`.

Now the remaining parts of `l1` and `l2` to be scanned are:
`l1`: `3->8->9` and `l2`: `2->5->7`.

We will append to `1` the smaller node between the above two, which is `2`.
This makes the list as: `1->2`.

Now the remaining parts of `l1` and `l2` to be scanned are:
`l1`: `3->8->9` and `l2`: `5->7`.

Keep comparing the above until 1 of the 2 lists end. After 3 more comparisons, the merged list is `1->2->3->5->7`, `l1` is `8->9` and `l2` has ended.

Since both the given lists were sorted we just need to set `next` of the last node of the merged list (`7`) to the first node of remaining part of `l1` (`8`). This gives the final merged list as:
`1->2->3->5->7->8->9`

Algorithm

1. Find the smaller node by comparing `val` of l1 and l2. Store that node as `head`.
2. Copy head to a temporary variable `temp`. Keep iterating until both lists have a `next` ListNode and assign the `next` node to the node with the smaller value among both lists.
3. When one of the lists finishes, append the remaining nodes of the other list to `temp`.

Python

``````class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
# if both lists are empty
if not l1 and not l2:
return None
# if one of the lists is empty
if not l1 or not l2:
return l1 if l1 else l2
if l1.val <= l2.val:
l1 = l1.next
else:
l2 = l2.next
# build remaining list
while l1 and l2:
if l1.val <= l2.val:
temp.next = l1
l1 = l1.next
else:
temp.next = l2
l2 = l2.next
temp = temp.next
# when one of the 2 lists ends, append the remaining list to temp
if l1:
temp.next = l1
if l2:
temp.next = l2

• Time complexity : \$\$O(m+n) \$\$, where `m` and `n` are the size of `l1` and `l2` respectively. We are iterating both the lists only once in the while loop.