平铺多层链表

Question

问题

1. 给定一个链表，除了next指针外，每个节点还有一个child指针，该指针可能指向另一个单独的链表。

2. 给定第一个链表的头节点，将链表展开，使所有节点都出现在单层链接列表中。

目标.

我们需要以这样的方式展开列表，即首先显示所有第一级节点，然后是第二级节点，依此类推。

上述列表应转换为

10->5->12->7->11->4->20->13->17->6->2->16->9->8->3->19->15

我的方法：

1) Create an empty queue
2) while(Queue is not empty AND head.next!=null AND head.child!=null)
     2a) while(head!=null)
           if(head.child!=null)
               Enqueue(head.child)
           newList = head;
           head = head.next;
           newList = newList.next;
     2b)head = deQ();

这种方法正确吗？

- Dubby

---

这是伪代码，但Queue is not empty是否等同于head.next!=null AND head.child!=null仍然不确定。除此之外，你的方法看起来是正确的。 - aa333

有一种双指解决方案，可以在不需要额外数据结构的情况下工作。（好吧，它需要两个手指，但它们只是节点指针。）我假设这是一份作业，你更愿意自己想出来对吧？ - rici

@rici 这不是作业。另外，你或者 @aa333 能不能指出 while 的第二行中的终止条件？ - Dubby

@Dubby：好的，解决方案已添加。我确定在Stack Overflow的其他地方也提供了相同的BFS算法。还有一种使用子链接来维护递归栈的两指深度优先版本；你可能会喜欢尝试弄清楚它。 - rici

Answer 1

这是一个简单的双指针广度优先（层序）遍历，可以进行就地展开。 （效率狂热者可能想要重新排列循环，因为有些测试会重复执行，但这几乎没有影响。）基本思想是存在一个隐式队列，由 finger2 和 finger1 之间的节点组成。 finger1 沿着层向前移动，每次到达没有右兄弟的节点时，“队列”通过将 finger2 向右移动直到找到一个子节点来扩展，然后将其附加在 finger1 处，以便 finger1 可以继续向右移动。

finger1 = finger2 = head;
while finger2 is not Null:
  while finger1.next is not Null: finger1 = finger1.next
  while finger2 is not Null and finger2.child is Null: finger2 = finger2.next
  if finger2 is not Null:
    finger1.next = finger2.child
    finger2.child = Null   

- rici

Answer 2

这是一个基于栈的简单解决方案，它遍历到下一个结束，然后将栈中的子元素添加进去。

node *flatten(node *head) {
    stack<node *> s;
    node *curr = root;
    while (1) {
        if (curr->next) { // keep moving in current streak
            if (curr->child)
                s.push(curr);
            curr = curr->next;
        }
        else { // attach child branch and continue from there
            if (s.empty())
                return head;
            curr->next = s.top()->next;
            s.top()->next = NULL;
            s.pop();
            curr = curr->next;
        }
    }
}

- Vishal Sahu

---

你的解决方案在给定的测试用例上失败了。此外，如果头部为空，它将崩溃。 - crisron