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:
resultandresult_tailare two variables that happen to point at the same value- Mutation / Changing of the underlying value (
result_tail.next = ListNode(1)) will affect the value shown byresult - However, assigning / pointing the variable
result_tailto another value will NOT affect the value ofresult result_tail = result_tail.nextis 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 Python's pass-by-object reference style https://stackoverflow.com/a/33066581/12295149
- Question asking on Python's object reference style Understanding Python's call-by-object style of passing function arguments
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:
resultandresult_tailare two variables that happen to point at the same value- Mutation / Changing of the underlying value (
result_tail.next = ListNode(1)) will affect the value shown byresult - However, assigning / pointing the variable
result_tailto another value will NOT affect the value ofresult result_tail = result_tail.nextis 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 Python's pass-by-object reference style https://stackoverflow.com/a/33066581/12295149
- Question asking on Python's object reference style Understanding Python's 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.
- 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) + "})"
- 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:]))
- 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))
python - How to convert ListNode from LeetCode to regular list? - Stack Overflow
How does ListNode work in LeetCode?
An easy leetcode question
How to understand the data structure of Python Linked List in Leetcode - Stack Overflow
The question doesn't require you to use regular lists. Since the lists are stored in "reverse order", that actually helps because you would add digits individually between both lists, then calculate/carry overflows moving left-to-right. For example, adding linkedlists [5, 1] + [5] would cause you to add one node to the resulting list [0, , then you iterate to the next position, carrying forward the 10s digit, then do 1 from your input plus 1 from the carry of the previous iteration, getting 2 , so the result is [0, 2]. If you carry a 1 into a 9, then you bring the carry digit forward again
Besides, if you're going to build a regular list, you might as well convert to an int, instead, do the math, then turn the int into the linked list...
But to convert a LinkedList into a regular list, without that LinkedList class being an iterable type itself, would look like this
ll = ListNode(...)
l = []
n = ll
while n is not None:
l.append(n.val)
n = n.next
Otherwise, if it were a proper Python iterable type, [n.val for n in ll]
You can patch iterability into those linked lists with this:
def ll_iter(node):
while node:
yield node.val
node = node.next
ListNode.__iter__ = ll_iter
Then in your code you can just do:
l1 = list(l1)
But I think it's simplest to just write a recursive solution working with the linked lists directly. You don't even get recursion depth problems, as the lists are guaranteed to have at most 100 nodes.
I've decided to tackle my first medium problem on Leetcode, Add Two Numbers (Java), but I've hit a wall. I started by reading the task and looking at the description, but after doing some research I just can't grasp how the ListNode class works. Here is its code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/I understand that it is supposed to work similar to the java.util.LinkedList class, but I don't get how. It holds two methods besides the default constructor and they only seem to set the values of int val and ListNode next. I am lost at how this chunk of code creates a singly-linked list, as I learned how to use one, but not how it works under the hood. I thought maybe it had something to do with the keyword "this", but after researching even more I learned that it is used to refer to the class property and not the parameter.
Also, while I was working on this I also wondered, is there a way to check the class files for the standard library or any other library? I want to check the code for the LinkedList and other classes in the future for clarity.
Drawing diagrams helps. Here's your linked list:
[ ]
|
v
[ ]
|
V
[ ]
|
V
None
Each arrow leading from a box represents the next attribute of that node.
Here are the three variables a, b, and c:
[ ] <-- a
|
v
[ ] <-- b
|
V
[ ] <-- c
|
V
None
Each of these variables also points to a particular node.
If you say b.next = None, the next attribute of the node referenced by b is modified, like this:
[ ] <-- a
|
v
None <-- [ ] <-- b
[ ] <-- c
|
V
None
This modifies the structure of the list. If you just set b itself to a different value, though, this is what happens:
[ ] <-- a
|
v
None <-- [ ] b --> None
[ ] <-- c
|
V
None
You changed b, but the node that b used to point to stays right where it was. Note that this is similar to how the c node continued to exist even after you set b.next = None.
Python doesn't have double pointers e.g. **x
b.next = c
print(a) # a is 1 -> 2 -> 3
b.next = None
E.g. in above, it doesn't mean c is None
When a.next is b, if you change a.next.next you are effectively changing b.next
But if you change a.next to None, it will not set b to None
Edit:
Also when you set b = None but a.next still points ListNode(2)
Hello all, I completed my 12th this may( high school graduate ) going to attend Engineering classes from next month. So I decided to start LeetCode question. Till now I have completed about 13 questions which includes 9 easy ones, 3 medium ones and 1 hard question( in python language ) with whatever was thought to me in my school, but recently I see many questions in from ***ListNode***, but searching in youtube doesn't shows anything about ListNode but only about Linked list. So kindly suggest me or provide the resources to learn more about it.
Thank you!