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
 Find the smaller node by comparing
val
of l1 and l2. Store that node ashead
.  Copy head to a temporary variable
temp
. Keep iterating until both lists have anext
ListNode and assign thenext
node to the node with the smaller value among both lists.  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
# find head
if l1.val <= l2.val:
head = l1
l1 = l1.next
else:
head = l2
l2 = l2.next
# build remaining list
temp = head
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
return head
Complexity Analysis

Time complexity : $$O(m+n) $$, where
m
andn
are the size ofl1
andl2
respectively. We are iterating both the lists only once in the while loop. 
Space complexity : $$O(1)$$. We don't need any extra space as we are merging the lists in place.