algorithm - 展平多级链表

Question

问题

1. 给定一个链表，其中除了下一个指针外，每个节点有一个子指针，它可能指向也可能不指向一个单独的列表。

2. 给定第一个列表的头部，将列表展平，以便所有节点出现在单级链表中。

Goal.

We need to flatten the list in such a way that all nodes at first level should come first, then nodes of second level, and so on.

上面的列表应该转换成

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();

这种方法是否正确？

Answer 1

这是一个简单的两指广度优先(级别顺序)遍历，它执行就地展平。 (效率怪胎可能想重新安排循环，因为有些测试进行了两次，但这几乎没有什么区别。)基本思想是有一个隐式队列，由 finger2 和 之间的节点组成>手指 1。 finger1 在关卡中向前走，每次到达没有右兄弟的节点时，“队列”通过向右走 finger2 前进，直到找到一个 child ，然后将其附加到 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