LeetCode Merge sorted linked list -- how does this code work?

Question

I’m working on the LeetCode problem: merge 2 sorted linked lists:

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

I couldn’t solve it, so I looked at an answer that worked. I’d like to dissect it and learn:

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # *
        while list1 and list2:  # **            
            if list1.val < list2.val:
                cur.next = list1
                list1, cur = list1.next, list1  # ***
            else:
                cur.next = list2
                list2, cur = list2.next, list2
                
        if list1 or list2:  # ****
            cur.next = list1 if list1 else list2
            
        return dummy.next  # *****

The parts with asterisks are where I have questions:

is ListNode() a kind of function? what does it do?
does while list1 and list2 mean : if list1 and list2 is not blank?
list1, cur=list1.next, list1, is this supposed to mean that the entire list1 equals to the next value in list1? And the current node equals to the entire list1?
does if list1 or list2: cur.next = list1 if list1 else list2 mean that if either list is empty, the next node will be the non empty list?
for : return dummy.next, I thought you’re supposed to return an entire merged linked list, isn’t returning dummy.next just returning one node?

I’m new to linked lists

trincot · Accepted Answer · 2023-01-25 09:54:03Z

0

is ListNode() a kind of function? what does it do?

ListNode is a class. The template code that is presented to you has a comment block that has its definition:

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

With ListNode() the constructor (__init__) is called. As no arguments are passed, the created node will have its val attribute set to 0 and its next attribute to None.

does while list1 and list2 mean : if list1 and list2 is not blank?

Since list1 and list2 are either instances of the ListNode class or are None, this condition checks that neither is None and the loop will repeat as long as that is the case. When at least one of them becomes None this condition will end the loop.

list1, cur=list1.next, list1, is this supposed to mean that the entire list1 equals to the next value in list1? And the current node equals to the entire list1?

This is a tuple assignment, i.e. two assignments happen. You could write the following equivalent code:

cur = list1
list1 = list1.next

The assignment to cur means that cur now references the (first) node of list1. The assignment to list1 means that it will reference the successor of that node. You could say that list1 now references a list that has one less node.

does this mean that if either list is empty, the next node will be the non empty list?

if list1 or list2 is executed after the loop. At that moment we know that at least list1 or list2 is None. This if checks if there is still one that is not None. If so, those nodes still need to be added to the merged result. And that is achieved with:

cur.next = list1 if list1 else list2

cur is always referencing the last node in the merged list. By assigning to cur.next we will append the remaining nodes to the merged list. The assigned value is either list1 or list2 whichever is the non-empty list. It could also have been written as:

cur.next = list1 or list2

return dummy.next, I thought you’re supposed to return an entire merged linked list, isn’t returning dummy.next just returning one node?

Initially, dummy.next is None, but as cur is initialised as a reference to that node and in the loop cur.next is assigned a node, we actually update that next attribute. Then the loop makes cur reference that node, and in a next iteration that node also gets a next...etc, and so the merged list is being chained together.

You may also want to read Merging two linked lists - how does the dummy node get updated?

answered Jan 25, 2023 at 9:54

trincot

357k38 gold badges282 silver badges338 bronze badges

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

4 Comments

kakashiz yo Over a year ago

i asked a separate question to see if i can get more clarification and make linked list more simple so i can understand, . so for the template code in this question: why would we create a function that passes no arguments? and is the template function generally required to create another function that can traverse through a linked list?

kakashiz yo Over a year ago

whyis the value set to 0 and next set to none

trincot Over a year ago

There are many reasons why you would call a function without arguments. In this case the function returns a new node object. I have explained in my answer what happens when no arguments are passed. The value is set to 0 because the value of that node is not relevant for what this node is used for. The next reference is set to None because the node starts by being alone -- not connected to another node. That connection is set later in the loop, when the value of that next is changed to a reference to another node.

trincot Over a year ago

Did you read the post that I linked to at the end? It visualises the whole process. I think it is quite helpful to understand what happens. (In that post the node gets value -1 instead of 0, but it doesn't matter).

Collectives™ on Stack Overflow

LeetCode Merge sorted linked list -- how does this code work?

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related