Flatten a multilevel doubly linked list

Linked List Depth-First Search Doubly-Linked List

62.6% acceptance

Jan 13, 2026

5438

349

You are given a doubly linked list with nodes that have a next pointer, a previous pointer, and an additional child pointer. Flatten the list so that all nodes appear in a single-level list.

Solution

C++

Time O(n)

Space O(1)

LeetCode

solution.cpp

class Solution {
public:
  Node* flatten(Node* head) {
    Node* curr = head;
    while (curr) {
      if (curr->child) {
        Node* child = curr->child;
        Node* next = curr->next;
        curr->next = child;
        child->prev = curr;
        curr->child = nullptr;
        Node* tail = child;
        while (tail->next) tail = tail->next;
        tail->next = next;
        if (next) next->prev = tail;
      }
      curr = curr->next;
    }
    return head;
  }
};