linked list – Python Logic of ListNode in Leetcode

linked list – Python Logic of ListNode in Leetcode

The short answer to this is that, Python is a pass-by-object-reference language, not pass-by-reference as implied in the question. It means that:

1. result and result_tail are two variables that happen to point at the same value
2. Mutation / Changing of the underlying value (result_tail.next = ListNode(1)) will affect the value shown by result
3. However, assigning / pointing the variable result_tail to another value will NOT affect the value of result
4. result_tail = result_tail.next is assigning the next node of the node that is currently assigned by the variable

The following is an visualization of the values that are assigned to the variables (r = result, rt = result_tail):

result = ListNode(0)
#r
#0 -> None

result_tail = result
#r
#0 -> None
#rt

result_tail.next = ListNode(1)
#r
#0 -> 1 -> None
#rt

result_tail = result_tail.next
#r
#0 -> 1 -> None
#     rt

result_tail.next = ListNode(2)
#r
#0 -> 1 -> 2 -> None
#     rt

result_tail = result_tail.next
#r
#0 -> 1 -> 2 -> None
#          rt

References for additional reading:

• An article explaining the Python pass-by-object reference style in detail https://robertheaton.com/2014/02/09/pythons-pass-by-object-reference-as-explained-by-philip-k-dick/
• An answer explaining Pythons pass-by-object reference style https://stackoverflow.com/a/33066581/12295149
• Question asking on Pythons object reference style Understanding Pythons call-by-object style of passing function arguments

For those reading this in the future: I wanted to debug linked list problems on a local environment so here is what I did.

1. Modified the Leetcode code for ListNode by including the dunder repr method. This is for when you want to print a ListNode to see what its value and next node(s).

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

    def __repr__(self):
        return ListNode(val= + str(self.val) + , next={ + str(self.next) + })

2. Next, I made a recursive function that makes a nested ListNode when you pass in a list. This is so you can test your methods by passing in lists (instead of having to manually make a confusing looking ListNode yourself.

def list_to_LL(arr):
    if len(arr) < 1:
        return None

    if len(arr) == 1:
        return ListNode(arr[0])
    return ListNode(arr[0], next=list_to_LL(arr[1:]))

3. Here is an example that tests my answer for the reverseList problem:

def reverseList(head: ListNode) -> ListNode:
    prev = None
    while head:
        next_node = head.next
        head.next = prev
        prev = head
        head = next_node

    return prev


# test cases
t1 = list_to_LL([1, 2, 3, 4, 5])  #ListNode(val=1, next={ListNode(val=2, next={ListNode(val=3, next={ListNode(val=4, next={ListNode(val=5, next={None})})})})})
t2 = list_to_LL([1, 2])  #ListNode(val=1, next={ListNode(val=2, next={None})})
t3 = list_to_LL([])

# answers
print(reverseList(t1))
print(reverseList(t2))
print(reverseList(t3))

linked list – Python Logic of ListNode in Leetcode

First, thank you so much for posting this question. I worked on the same problem and saw this piece of code and was puzzled too. Then I followed some comments from leetcode and came here.

I realize that my problem was that I didnt have a pen and paper earlier. After I drew the linked list on the paper by following the loop, it turned out to be quite clear.

If you are still not clear about this, please try to draw the linked list by following the logic. Not sure if I got the right term here but below is my understanding.

To be honest, I do not think this is related to pass by reference or value. To me, this is just about two variables being assigned with the same value(memory location) at the beginning. Think of variables as storage of address. Address is the real memory location which is the start of some value. Later on, one variable(result_tail) kept getting reassigned to a different location and one(result) stays the same.

Result and result_tail both point to the location of 0|None before the while loop.
0|None grew into 0->7|None, then 0->7->0|None and at last 0->7->0->8|None by result_tail.next being assigned every time. Result_tail gets reassigned so value changed during each loop, but result points to the same location which is the 0->.... Thus the result.