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

a = ListNode(5)
b = ListNode(10)
c = ListNode(20)


e = ListNode(0)
f = ListNode(5)
g = ListNode(21)
h = ListNode(30)


a.next = b
b.next = c

e.next = f
f.next = g
g.next = h

So I have two singly linked lists with heads a and e

I want to merge in ascending order of their values. For now, I want to merge them be iterating through both the linked lists, comparing values UNTIL one of the linked lists reaches None (one of the linked lists are shorter than the other and so one will reach None before the other)

class Solution:
    def mergeTwoLists(self, l1, l2):

        tempNode = ListNode(0)
        returnNode = tempNode

        while (l1.next != None) and (l2.next != None):



            if l1.val < l2.val:

                print("l1.val < l2.val", l1.val, l2.val)
                tempNode.next = l1

                tempNode = tempNode.next
                l1 = l1.next

            elif l1.val == l2.val:

                print("l1.val == l2.val", l1.val, l2.val)

                #If both the values are equal, assign l1's value first
                #then make l2's value follow l1's value using tempNode 

                tempNode.next = l1 
                tempNode = tempNode.next #Because of the previous statement, after execution of this statement, I'm assuming tempNode.val is now l1.val and tempNode.next = l1.next

                #tempNode.next is supposed to be equal to l1.next, instead assign it to l2
                tempNode.next = l2
                tempNode = tempNode.next #Because of the previous statement, after execution of this statement, I'm assuming tempNode.val is now l2.val and tempNode.next = l2.next

                #Increment both l1 and l2
                l1 = l1.next
                l2 = l2.next


            else:
                print("l1.val > l2.val", l1.val, l2.val)
                tempNode.next = l2

                tempNode = tempNode.next
                l2 = l2.next

sol = Solution()
sol.mergeTwoLists(a, e)

So here's what I would ideally like to happen but clearly is NOT happening as you will see when you print the statments!

l1.val = 5 > l2.val = 0

increment or move forward with l2!

l1.val = 5 which is == l2.val == 5

they are both equal, so move l1 to it's next AND l2 to it's next

Now, l1.val should be 10 and l2.val should be 21, but l1.val is being printed as 5 and l2.val is being printed as 21 and stuck in some infinite loop..

Why does l1.val stay at 5 instead of being updated to 10 and why does it stay in this infinite loop instead of one of them reaching their ends according to my while statement?

Improve this question

2 Answers 2

Reset to default
2

Problem is in the following code fragment

tempNode.next = l1 
tempNode = tempNode.next 
tempNode.next = l2
tempNode = tempNode.next
l1 = l1.next
l2 = l2.next

Just change it to the following, your code will work

tempNode.next = l1 
tempNode = tempNode.next
l1 = l1.next 
tempNode.next = l2
tempNode = tempNode.next
l2 = l2.next

Problem with your approach is that when you do tempNode.next = l2 you're modifying the actual ListNode that is pointed by l1 which make you stuck in an infinite loop

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

You need to assign l1 and l2's values to tempNode.val instead of assigning l1 and l2 nodes themselves to tempNode's next node. You also need to add l1 or l2's remaining values to tempNode if the other list is empty.

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

a = ListNode(5)
b = ListNode(10)
c = ListNode(20)


e = ListNode(0)
f = ListNode(5)
g = ListNode(21)
h = ListNode(30)


a.next = b
b.next = c

e.next = f
f.next = g
g.next = h

class Solution:
    def mergeTwoLists(self, l1, l2):

        returnNode = tempNode = ListNode()

        while l1 or l2:
            if not l1:
                print('l1 is empty; adding value from l2:', l2.val)
                tempNode.val = l2.val
                tempNode.next = ListNode()
                tempNode = tempNode.next
                l2 = l2.next
            elif not l2:
                print('l2 is empty; adding value from l1:', l1.val)
                tempNode.val = l1.val
                tempNode.next = ListNode()
                tempNode = tempNode.next
                l1 = l1.next
            elif l1.val < l2.val:

                print("l1.val < l2.val", l1.val, l2.val)
                tempNode.val = l1.val

                tempNode.next = ListNode()
                tempNode = tempNode.next
                l1 = l1.next

            elif l1.val == l2.val:

                print("l1.val == l2.val", l1.val, l2.val)

                #If both the values are equal, assign l1's value first
                #then make l2's value follow l1's value using tempNode

                tempNode.val = l1.val
                tempNode.next = ListNode() #Because of the previous statement, after execution of this statement, I'm assuming tempNode.val is now l1.val and tempNode.next = l1.next
                tempNode = tempNode.next

                #tempNode.next is supposed to be equal to l1.next, instead assign it to l2
                tempNode.val = l2.val
                tempNode.next = ListNode() #Because of the previous statement, after execution of this statement, I'm assuming tempNode.val is now l2.val and tempNode.next = l2.next
                tempNode = tempNode.next

                #Increment both l1 and l2
                l1 = l1.next
                l2 = l2.next


            else:
                print("l1.val > l2.val", l1.val, l2.val)
                tempNode.val = l2.val

                tempNode.next = ListNode()
                tempNode = tempNode.next
                l2 = l2.next
        return returnNode

sol = Solution()
node = sol.mergeTwoLists(a, e)
while node and node.val is not None:
    print(node.val)
    node = node.next

This outputs:

l1.val > l2.val 5 0
l1.val == l2.val 5 5
l1.val < l2.val 10 21
l1.val < l2.val 20 21
l1 is empty; adding value from l2: 21
l1 is empty; adding value from l2: 30
0
5
5
10
20
21
30
Improve this answer

5 Comments

Thanks @blhsing! I had to accept pulkit's answer because it concisely addressed the problem I was facing. You also need to add l1 or l2's remaining values to tempNode if the other list is empty. I know I had to do this part, I purposely did not add this or ask this in the question because that would make it too lengthy. Thanks for your help, I've upvoted your answer too.
@Abhishek Did you try pulkit-singhal's code at all? It won't work. I modified a lot more than pulkit-singhal's answer to make your code work. Please examine the changes closely. The point is to assign l1 and l2's values to tempNode's value, not pointers. pulkit-singhal's answer is actually incorrect. Accepting his/her answer makes no sense.
pastebin.com/Kwz96zNk Here is the code! With his added part! It worked for the leetcode question that I'm dealing with! I had to change it the way pulkit posted it with the added change that instead of (l1.next != None) and (l2.next != None) in the while condition, I had to give it as (l1 != None) and (l2 != None). The pastebin link expires in one hour.
Yes, the while condition needs fixing like I did in my solution, but also your solution would alter both l1 and l2's lists along the way of building tempNode since you're reusing l1 and l2's nodes directly without instantiating new ones. But if you don't care about l1 and l2 being altered then I guess it's okay (after fixing the while condition)
Your answer is NOT wrong by any means! But because I'm a newbie to programming that it takes me time to see the difference between if f1: and if f1 == True: and so it gives me a brain freeze for a few seconds when you say if f1 or f2. I don't have much programming experience. His code simply dealt with the part of the code that needed fixing. I hadn't mentioned if it mattered if l1 or l2 were altered and I had ALSO mentioned that for now I didn't care about the rest of the unfinished linked list. So I'm sorry I'm not picking your answer. My lack of experience is the problem here.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.