Merging two sorted linked lists in Python

Question

I am solving a Leetcode question (Problem #21) that takes two sorted linked lists and returns a sorted, merged linked list. For example, Input: 1->2->4, 1->3->4 and Output: 1->1->2->3->4->4.

I am not super experienced with linked lists, but am trying to tackle more problems to gain exposure. Instead of returning the desired output, of [1,1,2,3,4,4], my code just returns [4]. However, I think the main logic is there, and I am hopefully missing something small.

def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        newList = ListNode(0) # used for single, merged list
        while l1 and l2:
            if l1.val <= l2.val: # compare current node's values
                newList.next = l1
                l1 = l1.next
            else:
                newList.next = l2
                l2 = l2.next

        return newList.next # first node is 0, which we don't want

Answer 1

The main logic is almost there but you are only replacing the next item in the list each time (you did not advance the list), thus you are only returning the last item. Solution is to create another 'cur pointer' for advancing the list while keeping newList as the 'front pointer' for returning the result.

Also at the end, you should 'concat' with the non-empty list

def mergeTwoLists(self, l1, l2):
    newList = ListNode(0)
    cur = newList 
    while l1 and l2:
        if l1.val < l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    cur.next = l1 or l2 # add non-empty list
    return newList.next