CODEWITHSUNDEEP
pythonlinked-list
user15552191
user15552191

Reputation:

why is the last element of the linked list not appearing in the output?

I have written some code relating to Linked Lists, ListNode class. The aim of a code is to merge two sorted linked lists into one large sorted linked list.

So, for example

Input: L1 = [1,2,4], L2 = [1,3,4]

Output: [1,1,2,3,4,4]

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        prehead = ListNode(-1)
        if l1 and l2 == None:
            return None

        if l1 == None:
            return l2

        if l2 == None:
            return l1

        prev = prehead
        curr1 = l1
        curr2 = l2

        while curr1 and curr2:
            if curr1.val <= curr2.val:
                prev.next = curr1
                curr1 = curr1.next 

            elif curr1.val >= curr2.val:
                prev.next = curr2
                curr2 = curr2.next
                
            prev = prev.next
                

        return prehead.next

The above code is returning [1,1,2,3,4] as the output rather than the correct answer [1,1,2,3,4,4], and I know why; it is because when we get to the last element of L1, the while loop stops and doesn't take into account the last element of L2.

I have tried to change the code, in particular the 'while curr1 and curr2' line to read 'while L1 and L2':....

But this produced an AttributeError for the following line "if curr1.val < curr2.val:" NoneType object has no attribute 'val'.

Any ideas 1. how to amend the code to produce the right output and 2. why I am getting that error when I change the while line?

Thanks

Upvotes: 0

Views: 132

Answers (1)

antdul
antdul

Reputation: 396

the problem actually comes from the while because with the "and" when one of the two lists no longer has an element, we must therefore use "or" and handle the case where a list is empty:

while curr1 or curr2:
    if curr1 and (not curr2 or curr1.val <= curr2.val):
        prev.next = curr1
        curr1 = curr1.next 

    elif not curr1 or curr1.val >= curr2.val:
        prev.next = curr2
        curr2 = curr2.next
                
    prev = prev.next

Upvotes: 1

Related Questions