class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode()
prev_group = dummy
while head:
j, group_end = 1, head #start of group = end after reverse
while j < k and head.next:
head = head.next
j+=1
group_start = head #end of group = start after reverse
next_group = head = head.next #start of next group
if j != k: #don't need reverse (not enough nodes)
break
#reverse current group without links to prev and next groups
prev, cur = None, group_end
while cur != next_group:
cur.next, cur, prev = prev, cur.next, cur
prev_group.next = group_start
prev_group = group_end
group_end.next = next_group
return dummy.next
This is a solution proposed by others I found on the solution platform in Leetcode.
I do not understand the last three lines of code in the while loop. Why do i need to "prev_group.next=group_start", if I am going to assign group_end to prev_group in the next line? If I have a linked list of 1->2->3->4->5, the next attribute in group_end is going to be 2, so won't the prev_group.next be overwritten by 2. So in the end what is the use of the prev_group.next = group_start. An additional question is are all the head, group_end, next_group variables are all of them pointers, nodes or part of the linked list. If I am not mistaken, unlike in C, python3 doesn't not have pointers. So both the variables like head is a node , their next attribute is also a node, however their not part of the linked list or else when i assign head.next to head, won't I remove the head of the link list in the process?
Why do I need to do
prev_group.next=group_start
, if I am going to assigngroup_end
toprev_group
in the next line?
When you assign some to a variable, it never affects the linked list, but only that variable. Whatever previous value that variable had is of no importance. The first assignment you quote is different: it doesn't assign to a variable, but to an attribute. This kind of assignment mutates a data structure. So the goal of these assignments is quite different. The first one is intended to apply some "rewiring" to the linked list, while the second one is intended to reference a different node in the list as a preperation for the next iteration of the loop. It doesn't do anything to the linked list.
It may help to visualise the process. Let's take as example input a linked list with values 1, 2, 3, 4 and 5, and have π equal to 2. Then when the dummy node has been created, we get into the outer while
loop, and after initiliasing j
and group_end
we have something like this state for the data structure:
dummy prev_group head group_end
β β β β
ββββ΄ββββββ΄βββ ββββββ΄βββββ΄ββ βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ
β val: 0 β β val: 1 β β val: 2 β β val: 3 β β val: 4 β β val: 5 β
β next: Noneβ β next: βββββββββ€ next: βββββββββ€ next: βββββββββ€ next: βββββββββ€ next: Noneβ
βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ
The first inner while
loop will iterate just once, because k
is 2. head
will have moved up to the next node. Note how head = head.next
does not update the data structure. It just makes head
reference the next node:
dummy prev_group group_end head
β β β β
ββββ΄ββββββ΄βββ ββββββ΄βββββββ βββββ΄ββββββββ βββββββββββββ βββββββββββββ βββββββββββββ
β val: 0 β β val: 1 β β val: 2 β β val: 3 β β val: 4 β β val: 5 β
β next: Noneβ β next: βββββββββ€ next: βββββββββ€ next: βββββββββ€ next: βββββββββ€ next: Noneβ
βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ
The next two statements initialise group_start
and next_group
and head
is advanced again:
dummy prev_group group_end group_start head next_group
β β β β β β
ββββ΄ββββββ΄βββ ββββββ΄βββββββ βββββ΄ββββββββ βββ΄βββββββ΄βββ βββββββββββββ βββββββββββββ
β val: 0 β β val: 1 β β val: 2 β β val: 3 β β val: 4 β β val: 5 β
β next: Noneβ β next: βββββββββ€ next: βββββββββ€ next: βββββββββ€ next: βββββββββ€ next: Noneβ
βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ
j
is 2, so the break doesn't occur, and prev
and curr
are initialised in preparation of the next inner while
loop:
dummy prev_group group_end group_start head next_group
β β β β β β
ββββ΄ββββββ΄βββ ββββββ΄βββββββ βββββ΄ββββββββ βββ΄βββββββ΄βββ βββββββββββββ βββββββββββββ
β val: 0 β β val: 1 β β val: 2 β β val: 3 β β val: 4 β β val: 5 β
β next: Noneβ β next: βββββββββ€ next: βββββββββ€ next: βββββββββ€ next: βββββββββ€ next: Noneβ
βββββββββββββ ββββββ¬βββββββ βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ
|
prev: None curr
That inner while
loop will make its first iteration. Note how a next
attribute is updated to take the value of prev
, which is None
. curr
itself advances to what originally its next
attribute referenced, and prev
takes the original reference that curr
had:
dummy prev_group group_end group_start head next_group
β β β β β β
ββββ΄ββββββ΄βββ ββββββ΄βββββββ βββββ΄ββββββββ βββ΄βββββββ΄βββ βββββββββββββ βββββββββββββ
β val: 0 β β val: 1 β β val: 2 β β val: 3 β β val: 4 β β val: 5 β
β next: Noneβ β next: Noneβ β next: βββββββββ€ next: βββββββββ€ next: βββββββββ€ next: Noneβ
βββββββββββββ ββββββ¬βββββββ βββββ¬ββββββββ βββββββββββββ βββββββββββββ βββββββββββββ
β |
prev curr
Note how prev
and next
will move in "tandem" to the right, while one link in the data structure is updated. There is a second iteration of the same loop, which again mutates the next
attribute of the node referenced by curr
, while both prev
and curr
move to the right:
dummy prev_group group_end group_start head next_group
β β β β β β
ββββ΄ββββββ΄βββ ββββββ΄βββββββ βββββ΄ββββββββ βββ΄βββββββ΄βββ βββββββββββββ βββββββββββββ
β val: 0 β β val: 1 β β val: 2 β β val: 3 β β val: 4 β β val: 5 β
β next: Noneβ β next: Noneβ β next: ββ β β next: βββββββββ€ next: βββββββββ€ next: Noneβ
βββββββββββββ βββββββββββ¬ββ βββββ¬βββββΌβββ ββββ¬βββββββββ βββββββββββββ βββββββββββββ
ββββββββββββββββ |
prev curr
At this point the nodes in the first group, i.e. between group_end
and group_start
have been reversed: group_start
and group_end
have become what their names suggest.
Now we get the the last three statements of the main loop. While up to know we took care of rewiring nodes within a group, these last statements take care of wiring one group to the next. This also achieves that the new head reference will be correct (which is taken from dummy.next
at the very end). prev_group.next=start
will make the necessary link, while prev_group=next_group
prepares the variable for the next iteration. We get:
prev_group
dummy group_end group_start head next_group
β ββββββββββββββββββββ β β β
ββββ΄βββββββββ β ββββββ΄βββββββ ββ΄βββ΄ββββββββ βββ΄βββββββ΄βββ βββββββββββββ βββββββββββββ
β val: 0 β β β val: 1 β β val: 2 β β val: 3 β β val: 4 β β val: 5 β
β next: βββββββ β next: Noneβ β next: ββ β β next: βββββββββ€ next: βββββββββ€ next: Noneβ
βββββββββββββ βββββββββββ¬ββ βββββ¬βββββΌβββ ββββ¬βββββββββ βββββββββββββ βββββββββββββ
ββββββββββββββββ |
prev curr
The assignment group_end.next = next_group
is intended to link the current group with the next group:
prev_group
dummy group_end group_start head next_group
β ββββββββββββββββββββ β β β
ββββ΄βββββββββ β ββββββ΄βββββββ ββ΄βββ΄ββββββββ βββ΄βββββββ΄βββ βββββββββββββ βββββββββββββ
β val: 0 β β β val: 1 β β val: 2 β β val: 3 β β val: 4 β β val: 5 β
β next: βββββββ β next: β β β next: ββ β β next: βββββββββ€ next: βββββββββ€ next: Noneβ
βββββββββββββ βββββββββββ¬ββ βββββ¬βββββΌβββ ββββ¬βββββ¬ββββ βββββββββββββ βββββββββββββ
β ββββββββββββββββ | |
β prev curr β
βββββββββββββββββββββββββββββββββ
At this point the diagram becomes a bit a mess, so lets reposition the nodes with values 1 and 2 which allows to flatten some lines. Also, we can omit prev
, next
, group_start
and group_end
as they will be re-initialised in the next iteration of the main loop. The next iteration of the loop only needs to know what prev_group
and dummy
reference:
dummy head prev_group
β β β
ββββ΄βββββββββ βββββββββββββ βββββββββββββ βββ΄βββββββ΄βββ βββββββββββββ βββββββββββββ
β val: 0 β β val: 2 β β val: 1 β β val: 3 β β val: 4 β β val: 5 β
β next: βββββββββ€ next: βββββββββ€ next: βββββββββ€ next: βββββββββ€ next: βββββββββ€ next: Noneβ
βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ βββββββββββββ
Now we clearly see that the reversal of the first group was perfectly executed.
It is also clear (coming back to one of your questions) why prev_group
needed an assignment: the next iteration of the main loop uses this reference (and head
) to initialise the other variables. Sure, we could think of doing all this with maybe fewer variables, but they do help us to understand what is considered the current group, the previous group, the next group, what the first and last node are of the current group, ...etc, greatly helping to understand the code (in my opinion).
You could continue from here to draw the effect of a second iteration of the main loop, but I think the idea is clear and I shouldn't bore you further with an already lengthy post ;-)
Hope this clarifies it.