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 to create my own input for Python linked list questions? - Stack Overflow
How to understand the data structure of Python Linked List in Leetcode - Stack Overflow
Learning python in-depth as new interview language -- what is this "Optional [ListNode]"?
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.
You need two functions:
- One to turn a standard list into a linked list (for calling the
middleNode) - One to turn a linked list back into a list (for printing the result)
I would suggest to add methods to the ListNode class. The second one could actually be __iter__ so that a linked list becomes iterable, and then you just have to put the * operator in your print statement:
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
@classmethod
def of(Cls, lst):
head = None
for val in reversed(lst):
head = Cls(val, head)
return head
def __iter__(self):
head = self
while head:
yield head.val
head = head.next
class Solution(object):
def middleNode(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
head = ListNode.of([1,2,3,4,5])
print(*Solution().middleNode(head))
LeetCode lets you specify a linked list using Python list notation for convenience, since you can execute custom unit tests in the browser. The function doesn't actually take in a linked list; if you're running stuff locally, you have to convert from a vanilla Python list to a linked list.
The conversion you've done isn't quite right: what you've done is created a new ListNode that has its val field set to the list [1, 2, 3, 4, 5], and its next field set to None.
Here's what you're looking for (iterating over each element in the input list, and inserting them into a linked list):
def convert_to_linked_list(input_list):
head = None
for i in range(len(input_list) - 1, -1, -1):
new_head = ListNode(input_list[i], head)
head = new_head
return head
Edit: To print out the values in the linked list (as asked in a follow-up):
ll = convert_to_linked_list([1, 2, 3, 4])
current = ll
while current is not None:
print(current.val)
current = current.next
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)