展平单链表

Question

我有这个树结构，其中每个节点都有一个

next

和

child

指针。我正在尝试将这样的树展平为链表，其中每个节点仅使用

next

指针。

输入示例：

1 --> 2 --> 3 --> 4 --> 5 --> 6
            |
            V 
            7 --> 8 -- > 9 --> 10
                  |
                  V
                  11 --> 12

预期输出：

  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12

这是我的代码：

struct ListNode {
    int val;
    struct ListNode* next;
    struct ListNode* child;

    ListNode(int x) {
        val = x;
        next = NULL;
        child = NULL;
    }
};

ListNode* flatten(ListNode* head) {
    ListNode *temp = head, *r = NULL;
    while (temp) {
        if (temp->child) {
            r = temp->next;
            temp->next = flatten(temp->child);
        }
        if (!temp->next && r) {
            temp->next = r;
            r = NULL;
        }
        temp = temp->next;
    }
    return head;
}

问题

当我向它提供示例输入时，我的代码会陷入无限递归。

我的错误在哪里？

Answer 1

您的代码不会进入无限递归，而是进入无限循环。

存在以下问题：

• child

  指针永远不会清除到

  nullptr

  ，因此您得到的节点的

  child

  和

  next

  都指向同一个节点。当您还将尾部节点链接到上“级别”中的节点时，这最终会导致一遍又一遍地重新访问相同的

  child

  节点。如果您在递归调用返回后立即使用

  child

  清除

  temp->child = nullptr;

  指针，事情就不会陷入这样的循环。

• 虽然

  r

  保存了一个供以后重用的指针，但没有规定当同一“水平”列表中的多个节点具有非空

  child

  指针时：您的循环只能记住

  r 中的其中一个

  ，因此您将丢失信息。

• 逻辑优先链接子列表，在子列表连接到当前列表后返回“调用”列表。然而，您所需的输出优先于

  next

  列表，希望将子节点 after 放在这些列表之后。我假设这部分代码是错误的，并且您对预期输出的描述是正确的。

您可以通过仅跟踪列表的扁平部分的当前tail来完成此操作，而无需递归。

ListNode* getTail(ListNode* head) { // Assumes non-null argument
    while (head->next) {
        head = head->next;
    }
    return head;
}

ListNode* flatten(ListNode* head) {
    ListNode *tail = getTail(head);
    for (ListNode *node = head; node; node = node->next) {
        tail->next = node->child;
        tail = getTail(tail);
        node->child = nullptr;
    }
    return head;
}

与你的问题无关，但在C++中：

• 你不应该使用

  NULL

  但是

  nullptr

• struct ListNode

  可以只是

  ListNode

• 您可以为构造函数使用更短的 Member Initializer List 语法。

所以：

struct ListNode {
    int val;
    ListNode* next = nullptr;
    ListNode* child = nullptr;

    ListNode(int x): val(x) {}
}

最后，

flatten

将始终返回赋予它的参数，因此您可以考虑将其设为空函数。