Another day, another Leetcode July Challenge problem to look at. Today’s challenge is a pretty interesting linked list problem. We’re presented with multilevel doubly linked list and asked to flatten it. For example, for an input list such as:

1 ↔ 2 ↔ 3 → NULL
↓
4 ↔ 5 → NULL

We should return:

1 ↔ 4 ↔ 5 ↔ 2 ↔ 3 → NULL

Not too bad, but things get a little more complicated when you consider handling multiple, nested child levels. The initial instinct might be to reach for a recursive algorithm. The problem with this approach is that there is the potential for worst case O(n) levels of recursion on an input with an upper bound of 1000 nodes. I don’t like the sound of that. With just a little more work–read pointer manipulation–we can make a pretty good iterative algorithm.

Node* flattenRecursive(Node* head) {
   Node* current = head;
   while(current) {
	  if(current->child) {
		 Node* next = current->next;
		 current->next = flattenRecursive(current->child);
		 current->child = nullptr;

		 if(current->next) current->next->prev = current;

		 while(current->next) current = current->next;
		 current->next = next;
		 if(next) next->prev = current;
	  }
	  current = current->next;
   }
   return head;
}

vs.

Node* flattenIterative(Node* head) {
   Node* current = head;
   while(current) {
	  if(current->child) {
		 Node* next = current->next;
		 Node* child = current->child;
		 current->next = child;
		 child->prev = current;
		 current->child = nullptr;
		 while(child->next) child = child->next;
		 child->next = next;
		 if(next) next->prev = child;
	  }
	  current = current->next;
   }
   return head;
}

If you look closely, you’ll see that the algorithm will actually iterate over each element in any given sublevel twice–once when the sublevel is placed into the parent and again as the parent is iterated over in the outer loop. This gives us an iterative algorithm with the same asymptotic complexity, O(n), as a slightly simpler recursive algorithm, but without having to worry about the size of the recursive call stack. Note: there’s another potential iterative algorithm available wherein sublevel nodes could be moved onto a stack to handle multiple sublevels, but I don’t like that option quite as much as it suffers from a similar problem as the recursive algorithm, meaning memory usage of the stack would have a worst case O(n) complexity.