I am confused by the linked list and nodes in python. I am currently doing a question about reversing linked list in groups of k on leetcode

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?

Solution

Why do I need to do prev_group.next=group_start, if I am going to assign group_end to prev_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.