我对python中的链表和节点感到困惑。我目前正在leetcode上做一道关于在k组中反转链表的问题

问题描述 投票：0回答：1
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

这是我在Leetcode的解决方案平台上找到的其他人提出的解决方案。

我不明白 while 循环中的最后三行代码。如果我要在下一行中将 group_end 分配给 prev_group ，为什么需要“prev_group.next=group_start”？如果我有一个1->2->3->4->5的链表，那么group_end中的下一个属性将是2，那么prev_group.next不会被2覆盖。那么到底是什么呢？就是使用了prev_group.next = group_start。另一个问题是所有的 head、group_end、next_group 变量都是指针、节点还是链表的一部分。如果我没记错的话，与 C 不同，python3 没有指针。因此，像 head 这样的变量都是一个节点，它们的 next 属性也是一个节点，但是它们不是链表的一部分，否则当我将 head.next 分配给 head 时，我不会删除链表中的头过程？

python-3.x linked-list nodes
1个回答
0
投票

如果我要将 

prev_group.next=group_start
分配给下一行中的 
group_end
，为什么我需要执行 
prev_group
？

当您将一些值分配给变量时，它永远不会影响链表，而只会影响该变量。该变量以前的值是什么并不重要。您引用的第一个分配是不同的：它没有分配给变量，而是分配给attribute。这种赋值会“改变”数据结构。所以这些任务的目标是完全不同的。第一个旨在对链表应用一些“重新布线”，而第二个旨在引用列表中的不同节点作为循环下一次迭代的准备。它对链表没有任何作用。 这可能有助于可视化该过程。我们以输入一个值为 1, 2, 3, 4 和 5 的链表为例，并且 𝑘 等于 2。然后当创建虚拟节点时，我们进入外层 while 循环，并在初始化

后j

和 

group_end
我们有类似这样的数据结构状态：
 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│
└───────────┘   └───────────┘   └───────────┘   └───────────┘   └───────────┘   └───────────┘

第一个内部 
while
 循环将仅迭代一次，因为 
k
 是 2。
head
 将向上移动到下一个节点。请注意 
head = head.next
 不更新数据结构。它只是使 
head
 引用下一个节点：
 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│
└───────────┘   └───────────┘   └───────────┘   └───────────┘   └───────────┘   └───────────┘

接下来的两条语句初始化 
group_start
 和 
next_group
 并且 
head
 再次前进：
 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
 为 2，因此不会发生中断，并且 
prev
 和 
curr
 被初始化以准备下一个内部 
while
 循环：
 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

内部 
while
 循环将进行第一次迭代。请注意 
next
 属性如何更新以获取 
prev
 的值，即 
None
。 
curr
 本身前进到最初其 
next
 属性所引用的内容，并且 
prev
 采用 
curr
 所具有的原始引用：
 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

注意 
prev
 和 
next
 将如何“一前一后”向右移动，同时更新数据结构中的一个链接。同一循环有第二次迭代，它再次改变 
next
 引用的节点的 
curr
 属性，而 
prev
 和 
curr
 都向右移动：
 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

此时，第一组中的节点，即 
group_end
 和 
group_start
 之间的节点已颠倒过来：
group_start
 和 
group_end
 已变成其名称所示的样子。
现在我们得到主循环的最后三个语句。据了解，我们负责在一组中重新连接节点，最后这些语句负责将一组连接到下一组。这也使得新的头部参考将是正确的（取自最后的
dummy.next
）。 
prev_group.next=start
 将建立必要的链接，而 prev_group=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: None│   │ next: ─┐  │   │ next: ────────┤ next: ────────┤ next: None│
└───────────┘   └─────────┬─┘   └───┬────┼──┘   └──┬────────┘   └───────────┘   └───────────┘
                          └──────────────┘         |
                                  prev           curr

我们可以争论循环体中最后一条语句的必要性，因为它实际上只在最后的 
return
 语句之前才真正需要，即在循环完成之后。但这样做也没什么坏处
group_end.next = 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   │
                        └───────────────────────────────┘

此时图表变得有点混乱，因此让我们重新定位具有值 1 和 2 的节点，这样可以展平一些线条。另外，我们可以省略 
prev
 和 
next
，因为它们将在主循环的下一次迭代中重新初始化：


                                                     prev_group
 dummy            group_start    group_end      head next_group
   │                 │              │             │      │
┌──┴────────┐   ┌────┴──────┐   ┌───┴───────┐   ┌─┴──────┴──┐   ┌───────────┐   ┌───────────┐
│ val: 0    │   │ val: 2    │   │ val: 1    │   │ val: 3    │   │ val: 4    │   │ val: 5    │
│ next: ────────┤ next: ────────┤ next: ────────┤ next: ────────┤ next: ────────┤ next: None│
└───────────┘   └───────────┘   └───────────┘   └───────────┘   └───────────┘   └───────────┘

现在我们清楚地看到第一组的逆转被完美执行了。
您可以从这里继续绘制主循环的
第二次
迭代的效果，但我认为这个想法很清楚，我不应该用一篇已经很长的帖子让您进一步厌烦;-)


希望这能澄清这一点。

    




      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.