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.

CodePudding user response：

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;
            }
        }

2. 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

CodePudding user response：

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.