flatten_double_linked_list.cs

using System;

public class Program
{
	public class DoubleLinkedListNode
	{
		public DoubleLinkedListNode Next;
		public DoubleLinkedListNode Prev;
		public DoubleLinkedListNode Child;
		public int Value;
		public DoubleLinkedListNode(int val)
		{
			this.Value = val;
		}
	}

	public class ListFlattener
	{
		public DoubleLinkedListNode Tail;
		public DoubleLinkedListNode Head;

		public ListFlattener(DoubleLinkedListNode head, DoubleLinkedListNode tail)
		{
			this.Head = head;
			this.Tail = tail;
		}

		public void Flatten(DoubleLinkedListNode node, int level)
		{
			if (node.Child != null)
			{
				Flatten(node.Child, level + 1);
			}

			if (node.Next != null)
			{
				Flatten(node.Next, level);
			}

			if (level > 0)
			{
				AddNodeToTail(node);
			} else if (level == 0 && node.Child != null) {
				node.Child = null;
			}
		}

		public void AddNodeToTail(DoubleLinkedListNode node)
		{
			if (node.Prev != null && node.Prev.Next == node)
				node.Prev.Next = null;

			node.Next = null;
			node.Prev = Tail;
			node.Child = null;

			this.Tail.Next = node;
			this.Tail = node;
		}
	}

	public static void Main()
	{
		var level1_head = new DoubleLinkedListNode(5);
		var level1_node1 = new DoubleLinkedListNode(33);
		var level1_node2 = new DoubleLinkedListNode(17);
		var level1_node3 = new DoubleLinkedListNode(2);
		var level1_tail = new DoubleLinkedListNode(1);
		var level2_node1 = new DoubleLinkedListNode(6);
		var level2_node2 = new DoubleLinkedListNode(25);
		var level2_node3 = new DoubleLinkedListNode(6);
		var level2_node4 = new DoubleLinkedListNode(2);
		var level2_node5 = new DoubleLinkedListNode(7);
		var level3_node1 = new DoubleLinkedListNode(8);
		var level3_node2 = new DoubleLinkedListNode(9);
		var level3_node3 = new DoubleLinkedListNode(12);
		var level3_node4 = new DoubleLinkedListNode(5);
		var level4_node1 = new DoubleLinkedListNode(7);
		var level4_node2 = new DoubleLinkedListNode(21);
		var level4_node3 = new DoubleLinkedListNode(3);
		level1_head.Next = level1_node1;
		level1_head.Child = level2_node1;
		level1_node1.Prev = level1_head;
		level1_node1.Next = level1_node2;
		level1_node2.Prev = level1_node1;
		level1_node2.Next = level1_node3;
		level1_node3.Prev = level1_node2;
		level1_node3.Next = level1_tail;
		level1_node3.Child = level2_node4;
		level1_tail.Prev = level1_node3;
		level2_node1.Next = level2_node2;
		level2_node2.Prev = level2_node1;
		level2_node2.Child = level3_node1;
		level2_node2.Next = level2_node3;
		level2_node3.Prev = level2_node2;
		level2_node3.Child = level3_node2;
		level2_node4.Next = level2_node5;
		level2_node4.Child = level3_node3;
		level2_node5.Prev = level2_node4;
		level3_node2.Child = level4_node1;
		level3_node3.Next = level3_node4;
		level3_node3.Child = level4_node2;
		level3_node4.Prev = level3_node3;
		level4_node2.Next = level4_node3;
		level4_node3.Prev = level4_node2;

		var head = level1_head;
		var tail = level1_tail;

		(new ListFlattener(head, tail)).Flatten(head, 0);
		var node = head;

		while (true)
		{
			Console.WriteLine(node.Value);
			if (node.Next != null) {
				node = node.Next;
			} else {
				break;
			}
		}
	}
}