algorithm - 需要帮助可视化链接列表

Question

我一直在努力理解单向链表。

设置变量如

会有什么区别

cur=head
prev=head

对变量 cur 和 prev 做些什么？和

prev.next =cur.next 怎么样

影响链表？我如何可视化它？

    cur=head
    prev=head
    c=0
    while(end!=None):
        end=end.next
        c+=1
    print(c)
    mark=c-n
    if mark==0:
        head=head.next    

    while(mark>0):
        prev=cur
        cur=cur.next
        mark-=1
    prev.next=cur.next
    return head

Answer 1

在整个解释过程中，我们假设示例列表 1->2->3->4->5。

此算法从链表末尾删除第 n 个节点。代码的第一部分只是查找并打印列表的长度(我假设 c 是“count”的缩写):

c=0
while(end!=None):
    end=end.next
    c+=1
print(c)

注意这里少了一个变量end，它是用来遍历链表的runner节点，必须像end = head一样初始化。 end 遍历列表后，c = 5。

---

让我们来看看示例列表中的主要节点删除逻辑。第一部分，

if mark==0:
    head=head.next    

处理我们需要删除列表头部的边缘情况。 n 必须等于列表的长度，或者在本例中为 5，这意味着我们要删除倒数第 5 个节点。在这里，我们只是将 head 设置为其下一个元素，这会删除对 1 节点的所有引用。它将在这个操作之后的某个时刻被垃圾收集。

before:
+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
    ^    
    |    
   head

after:
+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
                ^    
                |    
               head

the resulting list:
+--------+  +--------+  +--------+  +--------+
| val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+
    ^    
    |    
   head

---

至于描述的典型案例

while(mark>0):
    prev=cur
    cur=cur.next
    mark-=1
prev.next=cur.next

如果要删除的元素不是头部，让我们来看一个 n = 2 的示例。在这种情况下，我们要从 1->2->3->4->5 或 4 中删除倒数第二个节点。

在 while 循环开始之前，这是 prev、cur 和 head 指向的内容:

   head
     |
     v
+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
  ^    ^
  |    |
prev  cur

在第一次迭代中，prev 设置为 cur:

+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
  ^    ^
  |    |
 prev cur

mark = 3

然后，cur 被设置为其下一个节点:

+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
    ^            ^
    |            |
   prev         cur

mark = 3

同样的事情再做两次:

+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
              ^    ^
              |    |
            prev  cur

mark = 2

+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
                 ^            ^
                 |            |
                prev         cur

mark = 2

+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
                          ^    ^
                          |    |
                         prev cur

mark = 1

+--------+  +--------+  +--------+  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  +--------+
                            ^            ^
                            |            |
                           prev         cur

mark = 1

此时，循环中断，因为 mark 递减为 0。您可以看到我们的节点处于完美的位置，可以使用 从列表中取消链接 4 >prev.next=cur.next。让我们开始吧:

                                   +------------------+
                                   |                  |
                                   |                  v
+--------+  +--------+  +--------+ |  +--------+  +--------+
| val: 1 |  | val: 2 |  | val: 3 | |  | val: 4 |  | val: 5 |
| next: --->| next: --->| next: ---+  | next: --->| next: ---> [None]
+--------+  +--------+  +--------+    +--------+  +--------+
                            ^              ^ 
                            |              |
                           prev           cur

cur 指向的值为 4 的节点是不可访问的，没有任何引用它。它将在将来的某个时候被解释器收集为垃圾。现在它不再是列表的一部分，当代码完成时我们得到这个结果:

+--------+  +--------+  +--------+  +--------+ 
| val: 1 |  | val: 2 |  | val: 3 |  | val: 5 |  
| next: --->| next: --->| next: --->| next: ---> [None]
+--------+  +--------+  +--------+  +--------+  
     ^
     |
   head