二项式堆兄弟——链表反转

Question

我不明白二叉堆中节点l的列表的反转：

Node* reverseList(Node* l) {
    //return reverseNode(l);
    if(l->sibling)
    {
        return reverseList(l->sibling);
        l->sibling->sibling = l;
    }
}

这是什么意思？ :

l->sibling->sibling = l;

parent?

Answer 1

问题中的代码不正确，这是正确的代码

int RevertList(Node *h){
    if (h->sibling != NULL){
        RevertList(h->sibling);
        (h->sibling)->sibling = h;
    }
    else
        root = h;
}

RevertList 是一个 helper-function 当节点从二项式堆中删除时使用。

当一个节点被删除时，它的子节点和它们的兄弟节点将从二项式堆结构中分离出来。 RevertList 函数反转分离子项的顺序，因此它们可以 union-ed 到根列表，以正确的顺序。

查看 this 代码以更好地理解其工作原理！

下面是来自 CLRS 教科书的示例

Answer 2

一条return语句结束了函数的执行，所以你问的是dead代码。

我希望函数实际上是这样的：

Node* reverseList(Node* l) {
    if (l->sibling)
    {
        Node* head = reverseList(l->sibling);
        l->sibling->sibling = l;
        l->sibling = NULL;
        return head;
    }
    return l;
}

为了形象化，举一个包含三个节点的链表示例：

  l
  ↓
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: ─────────► │ sibling: NULL │
│               │     │               │     │               │
└───────────────┘     └───────────────┘     └───────────────┘

当函数被调用时，我们进入if并进行递归调用。那个新的（第二个）执行上下文有它自己的局部变量，为了区分它们，我会在它们的名字上加上重音。所以我们有另一个 l' 变量：

  l                      l'
  ↓                      ↓
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: ─────────► │ sibling: NULL │
│               │     │               │     │               │
└───────────────┘     └───────────────┘     └───────────────┘

此外，该函数的执行将进行递归调用：

  l                      l'                   l"
  ↓                      ↓                    ↓
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: ─────────► │ sibling: NULL │
│               │     │               │     │               │
└───────────────┘     └───────────────┘     └───────────────┘

该函数的最新（第三次）执行获取 l'->sibling 作为参数并将其分配给它自己的局部变量 l"。它会发现 l"->sibling 是 NULL，所以它只是 return 相同的指针，没有做任何改变。此时变量 l" 的生命周期结束。调用者将 returned 值分配给本地 head' 变量——再次强调这发生在第二个执行上下文中：

  l                      l'                  
  ↓                      ↓                   
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: ─────────► │ sibling: NULL │
│               │     │               │     │               │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             head'

现在我们得到语句：l'->sibling->sibling = l'。这意味着对最后一个节点的 sibling 成员进行了赋值，因此我们得到：

  l                      l'                  
  ↓                      ↓                   
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: ─────────► │ sibling: ─┐   │
│               │     │               │ ◄───────────────┘   │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             head'

然后我们执行l'->sibling = NULL:

  l
  ↓ 
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: NULL │     │ sibling: ─┐   │
│               │     │               │ ◄───────────────┘   │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             head'

然后我们执行return head'。第二个执行上下文的变量结束了它们的生命（不再重音）。第一个执行上下文会将 returned 指针分配给它自己的 head 变量：

  l
  ↓ 
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: NULL │     │ sibling: ─┐   │
│               │     │               │ ◄───────────────┘   │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             head

现在我们得到语句：l->sibling->sibling = l。这意味着对中间节点的 sibling 成员进行了赋值，因此我们得到：

  l
  ↓ 
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: ─┐   │     │ sibling: ─┐   │
│               │ ◄───────────────┘   │ ◄───────────────┘   │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             head

我们执行l->sibling = NULL:

  l
  ↓ 
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: NULL │     │ sibling: ─┐   │     │ sibling: ─┐   │
│               │ ◄───────────────┘   │ ◄───────────────┘   │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             head

最后，我们 return head。局部变量结束了它们的生命周期，因此只有 returned 指针是相关的：

┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: NULL │     │ sibling: ─┐   │     │ sibling: ─┐   │
│               │ ◄───────────────┘   │ ◄───────────────┘   │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             (returned)

你可以看到 returned 指针确实引用了反向列表。

二项式堆兄弟——链表反转

Binomial heap sibling - linked list reversal

binomial-heap