1

So I'm struggling with how pointers work/are managed in Python. Specifically, I was working on a practice problem that takes in two sorted integer linked lists (min to max), and returns the merged, sorted linked list. I couldn't figure out how to do it after an hour of banging my head against the wall, so I found a solution online, specifically this:

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

I understand the main idea: check the value of the current nodes against each other, put the smaller one into the list and move that input list forward one node, then repeat. However, I'm struggling with cur and dummy, and how they work within this solution:

  1. Why does dummy.next link to cur? The entire function seems to only concern cur, and there's no explicit moving of the pointer of dummy to the head of cur like one would have to do in a language like C. I assume it has something to do with the fact that they're both initialized at the same time, but I don't quite understand how?

  2. Why do we update cur twice in consecutive lines? First we set cur.next equal to one of the lists, but then we set cur itself equal to that same list in the very next line? I don't understand why that is necessary, or even what it does in the construction of the linked list.

Improve this question
3
  • 1
    Python doesn't have pointers. This is very important to understand. Commented May 4, 2022 at 18:16
  • The key here is that this is not just merging list but merging sorted linked lists - and the way this is done is basically identical in any language. dummy should really be called head or pre_head or something like that. Mutating cur.next is something entirely different to changing cur itself. Commented May 4, 2022 at 18:16
  • Did you try using a debugger or code visualizer to understand what is happening at each step of the execution? Commented May 4, 2022 at 18:27

2 Answers 2

Reset to default
3

Every Python variable is a reference to a value; if you already understand how pointers work in C, then it might be useful to think of variables which reference mutable objects as working like C pointers. They aren't really the same thing, but a Python variable that references a ListNode acts a lot more like a C ListNode* than a C ListNode, so the pointer metaphor is a good conceptual starting point if that's the language you're coming from.

  1. dummy always points to the node that you created in the first line of the function, which is the same node that cur starts at. The first time you update cur.next, you are also updating dummy.next. cur is then reassigned to a new node, but the modification you made to dummy persists.

This Python code:

        cur = dummy = ListNode()
        while list1 and list2:               
            if list1.val < list2.val:
                cur.next = list1
                list1, cur = list1.next, list1

is essentially the same as:

        ListNode* cur, dummy;
        cur = dummy = new ListNode();
        while (list1 && list2) {               
            if (list1->val < list2->val) {
                cur->next = list1;
                cur = list1;
                list1 = list1->next;
            }
        }
  1. One is modifying the next attribute of the node that cur points to; the other is modifying cur itself to point at a new node.
                cur.next = list2
                cur = cur.next

is the same as:

                cur->next = list2;
                cur = cur->next;

For a more in-depth explanation of how exactly variables work in Python, read https://nedbatchelder.com/text/names.html

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

2 Comments

Thanks, this is very helpful for someone coming from C like myself! One quick follow up: if pointers don't exist in Python (as I have been informed), then what is the next field of the ListNode class? In C, it is always explicitly a pointer variable, but I don't understand how that translates to a Python context if there are no pointers in Python
It's an attribute, which is a type of variable, which, again, is sort of like a pointer, but not. You're not going to get a more satisfying answer than that without doing some reading. :) It's all actually pretty simple, but it'll take seeing a bunch of examples for it to sink in correctly, since it doesn't map perfectly to the concepts you're familiar with in C. (I went from C to Python and it took me a while to grok, partly because I was fumbling along on my own.) The link I included in my answer is very good at explaining it.
2

Why does dummy.next link to cur?

It does not.

Initially, an extra node is created, so that nodes from the source lists can be linked after it. dummy and cur are both names for that node, at the start of the function.

As the function progresses, cur becomes a name for different nodes, but dummy remains a name for the node that was originally created.

The function returns dummy.next, because the function worked by linking nodes in sequence after that node, and so dummy.next refers to (not "points at") the first of those linked nodes.

and there's no explicit moving of the pointer of dummy to the head of cur like one would have to do in a language like C.

There are no pointers in Python. Further, cur is a node; it does not have a "head". In this implementation, there are no objects that explicitly represent the overall list - only objects representing the nodes, such that the list is implicitly some node along with all the others reachable from it.

dummy started out being a name for a newly created node. There is no need to reassign dummy to be a name for "the head of the list", because it was a name for that node, never stopped being a name for that node, and that node was used as a predecessor for the list. (Since that node is not actually part of the intended result, we have to skip it when returning.)

Why do we update cur twice in consecutive lines?

First off, it is important to understand that we do not do so. In detail:

First we set cur.next equal to one of the lists, but then we set cur itself equal to that same list in the very next line?

Changing the value of cur.next is not the same kind of thing as setting cur itself. The same thing happens with, for example, list elements:

a = [1, 2, 3]
b = a
# changing an element of a WILL change what we see in b:
a[0] = 4
print(b)
# REPLACING `a` will NOT change what we see in b:
a = 'hi mom' # we don't even have to replace it with another list
print(b)

Writing b = a does not copy the list. It means that b is another name for the same thing that a names. If we change that thing, then obviously we will see the change if we inspect b. If we make a be a name for something else, then that will not impact b, because b is still a name for what it was before.

It is the same as actual names - or other forms of reference - of people in the real world. Bob is Alice's youngest son. When Bob grows up, Alice observes "my youngest son" grow up, because that means the same person. If Alice gives birth to another boy, and hugs "my youngest son", Bob does not feel the embrace - because "my youngest son" no longer means the same person.

I don't understand why that is necessary

Now we can consider the purpose of the code.

cur is a name we use for "the, currently, last node of the list we are constructing".

Since we add nodes to the list in order to construct it, this has to refer to different nodes over time.

By doing cur.next = ..., we link another node after the one that was named cur. That helps us to build the list, but now cur is no longer the name of the last node - because it is still the name of the node it was naming before, and that node isn't the last node any more, because we added a node.

So, after adding the node, we re-assign cur to name the node that we just added.

Improve this answer

1 Comment

Just to add: the reason for using a dummy node is so that handling the first node of the output works the same way as adding the other nodes - we make it the .next of something, and then next time through the loop we potentially make its .next be something else. It is possible to write the code in other ways. The author of the code had a particular aesthetic preference.

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.