Leetcode 21: Merge Two Sorted Lists

Code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        headbak = head = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                head.next = l1
                l1 = l1.next
            else:
                head.next = l2
                l2 = l2.next
                
            head = head.next
        
        while l1:
            head.next = l1
            l1 = l1.next
            head = head.next
        
        while l2:
            head.next = l2
            l2 = l2.next
            head = head.next
        
        return headbak.next

Idea

When two lists’ heads are not None, splice the smaller node into the new list and move the list’s head to the next of the smaller pointer. Then, when only one list’s head is not None, concatenate all of its remaining nodes.

See a harder version: Merge k sorted list: https//nb4799.neu.edu/wordpress/?p=926