Passing by reference and value in Python

Question

I'm doing a question from LeetCode. I've found something that doesn't make much sense to me.

The question:

Given a linked list, swap every two adjacent nodes and return its head.

For example, Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

My solution:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        dummy = ListNode(0)
        dummy.next = head
        curr = dummy

        while curr.next and curr.next.next:
            a = curr.next
            b = curr.next.next

            curr.next = b
            a.next = b.next
            b.next = a
            curr = a

        return dummy.next

The confusion:

When I do curr = dummy , it seems that dummy is passed by reference and mutating curr mutates dummy. But the return statement return dummy.next is not the same value as return curr.next? Since curr = dummy, at the end of the loop, curr is at the end of the list, so shouldn't dummy also be at the end of the list? However, dummy is still at the very front of the list and dummy.next is the start of the list passed into the function but mutated in the correct way.

Also, when I do:

        if curr is dummy:
            print("BEGIN")

        while curr.next and curr.next.next:
            a = curr.next
            b = curr.next.next

            curr.next = b
            a.next = b.next
            b.next = a
            curr = a

        if curr is dummy:
            print("END")

BEGIN gets printed but END doesn't.

Can someone clear the confusion up for me?

curr is the same as dummy initially, yes, but you set curr = a inside the loop, so curr won't remain the same as dummy. You're setting it to something else. Search this site for many, many questions about Python value/reference, variables, name binding, etc. — BrenBarn
– BrenBarn, Commented Aug 22, 2017 at 18:22
Please read Ned Batchelder's Facts and myths about Python names and values — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Aug 22, 2017 at 18:25

Danil Speransky · Accepted Answer · 2017-08-22 18:36:46Z

4

When you do an assignment var = x you make var point to x. It wouldn't make other variables pointed to the same object point to x after this.

Consider this example:

>>> a = {'p': 2}
>>> b = a
>>> b
{'p': 2}
>>> b['p'] = 4
>>> a
{'p': 4}
>>> b = {'q': 3}
>>> a
{'p': 4}
>>> b
{'q': 3}

Or this:

>>> class Node:
...     def __init__(self, nxt):
...         self.nxt = nxt
...     def __repr__(self):
...         return '(Node => %s)' % self.nxt
... 
>>> a = Node(Node(2))
>>> a
(Node => (Node => 2))
>>> b = a
>>> b
(Node => (Node => 2))
>>> a.nxt = Node(4)
>>> a
(Node => (Node => 4))
>>> b
(Node => (Node => 4))
>>> b = b.nxt
>>> a
(Node => (Node => 4))
>>> b
(Node => 4)

edited Aug 22, 2017 at 18:36

answered Aug 22, 2017 at 18:23

Danil Speransky

30.5k6 gold badges70 silver badges78 bronze badges

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

Collectives™ on Stack Overflow

Passing by reference and value in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related