Flatten a linked list with next and child pointers?

public class MultiLevelNode {

public int val;

public MultiLevelNode next;

public MultiLevelNode child;

public MultiLevelNode(int x) { val = x; next = null; child =

null; }

MultiLevelNode Flatten(MultiLevelNode head) {

if (head == null) return null;

MultiLevelNode dummy = new MultiLevelNode(0);

MultiLevelNode prev = dummy;

Stack<MultiLevelNode> stack = new Stack<MultiLevelNode>();

stack.Push(head);

while (stack.Count > 0) {

var curr = stack.Pop();

prev.next = curr;

curr.child = null; // remove child pointer after flattening

prev = curr;

if (curr.next != null) stack.Push(curr.next);

if (curr.child != null) stack.Push(curr.child);

return dummy.next;

Follow on:

Explanation:

Use a stack to perform DFS; attach nodes and remove child pointers.