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.
How to understand the data structure of Python Linked List in Leetcode - Stack Overflow
python - Linked list problem (Leetcode) - understanding inputs - Stack Overflow
Linked list in python
linked list - Python Logic of ListNode in Leetcode - Stack Overflow
Hello all,
I learned Data Structures in C, which I understood pretty good, but can't wrap around about them in Python as I am relatively new to DS in Python. I solved some DS questions in C before but I don't want to go back to C every time I get a DS problem. What needs to be done in this problem is to remove nth node from end of the linked list. What I wanted to do is to count total nodes and find the position from the start of the list and traverse two pointers, one which points the actual node to be bypassed/deleted and a previous node of which I will connect the "actual node"'s next node...but it doesn't seem to work.
Image for reference: https://ibb.co/jRy39k7
How I did is to make a curr pointer = head to count total nodes. After traversing, make a prev pointer = head and now set curr = head.next and traverse the list until the curr reaches the position required (which is given by i) and prev before curr.
Here are the things which I don't understand:
-
From what I understand, after the second while loop breaks, the curr is at node 4 with value 4 (shown in left top image) and prev is at node 3 and both (I think) clearly has a attribute called "val" but why is there an error in the left? You can see the values being printed below too.
-
You can also clearly see that there are only two print statements in the whole code but I am getting a total of 3 print outputs. Why is that?
Here's the code:
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
node_count = 0
curr = head
while True:
if curr is None:
break
node_count += 1
curr = curr.next
i = node_count-n-1
prev = head
curr = head.next
x = 0
while True:
if x >= i: break
curr = curr.next
prev = prev.next
x += 1
print(prev.val)
print(curr.val)
return headNOTE:
-
I clearly know that the code is incomplete, that I didn't actually delete the required node.
-
There maybe a better solution than mine but right now, I am only concerned with code to be working without any errors.
-
I have already tried using a for loop like for x in range(i) but same stuff.
Please help me, it would be a great favour.
Thank You
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)
could not get the concept of linked list in python can anybody help with the understanding of it ... genuinely have putted enough time but there is a gap in understanding of mine
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))