What is "groupPrev.next = kth" doing in this piece of code?-CodePudding

class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    groupPrev = dummy
    
    while True:
        kth = self.getKth(groupPrev, k) 
        if not kth:
            break
        groupNext = kth.next 
        curr = groupPrev.next 
        prev = kth.next 
        while curr != groupNext:
            tmp = curr.next 
            curr.next = prev 
            prev = curr
            curr = tmp
        
        tmp = groupPrev.next 
        groupPrev.next = kth    # <----- confusing!
        groupPrev = tmp
        
    return dummy.next 
        
def getKth(self, curr, k):
    while curr and k > 0:
        curr = curr.next 
        k -= 1
    return curr

CodePudding user response：

It may help to visualise it as follows. Lets say k=2 and the list is [1,2,3,4,5], then we get this state just before the inner loop starts:

                                        prev
 groupPrev    curr         kth          groupNext
  ↓            ↓            ↓            ↓
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐
│ val:  0 │  │ val:  1 │  │ val:  2 │  │ val:  3 │  │ val:  4 │  │ val:  5 │
│ next: ────>│ next: ────>│ next: ────>│ next: ────>│ next: ────>│ next: - │
└─────────┘  └─────────┘  └─────────┘  └─────────┘  └─────────┘  └─────────┘
  ↑            ↑
 dummy        head

When the inner loop exits after two iterations, we arrive in this state:

                           prev         
                           kth          curr    
 groupPrev                  ↓           groupNext 
  ↓                  ┌───────────────┐   ↓
┌─────────┐  ┌───────│─┐  ┌─────────┐│ ┌─────────┐  ┌─────────┐  ┌─────────┐
│ val:  0 │  │ val: 1│ │<┐│ val:  2 │└>│ val:  3 │  │ val:  4 │  │ val:  5 │
│ next: ────>│ next: ┘ │ ││ next: ┐ │  │ next: ────>│ next: ────>│ next: - │
└─────────┘  └─────────┘ │└───────│─┘  └─────────┘  └─────────┘  └─────────┘
  ↑            ↑         └────────┘      
 dummy        head

So now 2 is followed by 1 is followed by the next group. The only thing that is missing is that the previous group should not link to 1 but to 2. So that is why the following is needed:

groupPrev.next = kth
groupPrev = tmp

...and that will complete the job correctly linking the previous group to the current (reversed) group:

                           prev         
                           kth          curr    
              groupPrev     ↓           groupNext 
               ↓     ┌───────────────┐   ↓
┌─────────┐  ┌───────│─┐  ┌─────────┐│ ┌─────────┐  ┌─────────┐  ┌─────────┐
│ val:  0 │  │ val: 1│ │<┐│ val:  2 │└>│ val:  3 │  │ val:  4 │  │ val:  5 │
│ next: ┐ │  │ next: ┘ │ ││ next: ┐ │<┐│ next: ────>│ next: ────>│ next: - │
└───────│─┘  └─────────┘ │└───────│─┘ │└─────────┘  └─────────┘  └─────────┘
  ↑     │      ↑         └────────┘   │   
 dummy  │     head                    │
        └─────────────────────────────┘

If we redraw this by re-arranging where we place the reversed nodes, then the above is equivalent to this:

              prev                      curr    
              kth          groupPrev    groupNext 
               ↓            ↓            ↓
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐
│ val:  0 │  │ val: 2  │  │ val:  1 │  │ val:  3 │  │ val:  4 │  │ val:  5 │
│ next: ────>│ next: ────>│ next: ────>│ next: ────>│ next: ────>│ next: - │
└─────────┘  └─────────┘  └─────────┘  └─────────┘  └─────────┘  └─────────┘
  ↑                         ↑   
 dummy                     head

In the preparation of the next group's reversal we move some references, and right before the inner loop we get this:

                                                                  prev
                           groupPrev    curr         kth          groupNext 
                            ↓            ↓            ↓            ↓
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐
│ val:  0 │  │ val: 2  │  │ val:  1 │  │ val:  3 │  │ val:  4 │  │ val:  5 │
│ next: ────>│ next: ────>│ next: ────>│ next: ────>│ next: ────>│ next: - │
└─────────┘  └─────────┘  └─────────┘  └─────────┘  └─────────┘  └─────────┘
  ↑                         ↑   
 dummy                     head

And now we get the same effect of the inner loop, which makes again two iterations:

                                                     prev
                                                     kth          curr    
                           groupPrev                  ↓           groupNext 
                            ↓                  ┌───────────────┐   ↓
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌───────│─┐  ┌─────────┐│ ┌─────────┐
│ val:  0 │  │ val:  2 │  │ val:  1 │  │ val: 3│ │<┐│ val:  4 │└>│ val:  5 │
│ next: ────>│ next: ────>│ next: ────>│ next: ┘ │ ││ next: ┐ │  │ next: - │
└─────────┘  └─────────┘  └─────────┘  └─────────┘ │└───────│─┘  └─────────┘
  ↑                         ↑                      └────────┘
 dummy                     head

So now 4 is followed by 3 is followed by the next group. Again, the only thing that is missing is that the previous group should not link to 3 but to 4:

groupPrev.next = kth
groupPrev = tmp

...and that will lead to this:

                                                     prev
                                                     kth          curr    
                           groupPrev                  ↓           groupNext 
                            ↓                  ┌───────────────┐   ↓
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌───────│─┐  ┌─────────┐│ ┌─────────┐
│ val:  0 │  │ val:  2 │  │ val:  1 │  │ val: 3│ │<┐│ val:  4 │└>│ val:  5 │
│ next: ────>│ next: ────>│ next: ┐ │  │ next: ┘ │ ││ next: ┐ │<┐│ next: - │
└─────────┘  └─────────┘  └───────│─┘  └─────────┘ │└───────│─┘ │└─────────┘
  ↑                         ↑     │                └────────┘   │
 dummy                     head   └─────────────────────────────┘

In the next iteration kth will become None and so the task is completed. Only the correct reference needs to be returned:

return dummy.next

...which returns this list:

┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐
│ val:  2 │  │ val:  1 │  │ val:  4 │  │ val:  3 │  │ val:  5 │
│ next: ────>│ next: ────>│ next: ────>│ next: ────>│ next: - │
└─────────┘  └─────────┘  └─────────┘  └─────────┘  └─────────┘
  ↑
 (returned)

Hope this clarifies it.