"groupPrev.next = kth" 在这段代码中做了什么？

Question

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

https://leetcode.com/problems/reverse-nodes-in-k-group/

我用图表绘制了第一次迭代，希望这有助于解释代码。我知道 groupPrev 在这里是 dummy，所以这是否意味着说 groupPrev.next 也会改变 dummy.next，从而完全改变路径。但是说 groupPrev = tmp 对 dummy 没有影响？

想知道我的思考过程是否正确。我包含的图片会更好地解释！

Answer 1

将其可视化如下可能会有所帮助。假设 k=2 并且列表是 [1,2,3,4,5]，那么我们在内部循环开始之前得到这个状态：

                                        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

当内部循环在两次迭代后退出时，我们到达这个状态：

                           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

所以现在 2 之后是 1 之后是下一组。唯一缺少的是前一组不应该 link 到 1，而是到 2。所以这就是为什么需要以下内容：

groupPrev.next = kth
groupPrev = tmp

...这将正确地完成作业 link 将前一组转换为当前（反向）组：

                           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                    │
        └─────────────────────────────┘

如果我们通过重新安排放置反转节点的位置来重新绘制它，那么上面的内容等同于：

              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

在准备下一组的反转时，我们移动了一些引用，就在内部循环之前，我们得到了这个：

                                                                  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

现在我们得到了内部循环的相同效果，它再次进行了两次迭代：

                                                     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

所以现在 4 之后是 3 之后是下一组。同样，唯一缺少的是前一组不应该 link 到 3 而是到 4:

groupPrev.next = kth
groupPrev = tmp

...这将导致：

                                                     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   └─────────────────────────────┘

在下一次迭代中，kth 将变为 None，任务完成。只需要返回正确的引用：

return dummy.next

...returns 这个列表：

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

希望这能说明问题。

"groupPrev.next = kth" 在这段代码中做了什么？

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

python

linked-list

python-3.x