trekking-299000_640

Flatten a Linked List

Linked list is one of the most common data structures that are usually covered in coding interviews. Like I mentioned in our previous post, since data structures like binary tree, linked list have limited ways of operation, the problem usually can’t be too hard in an interview. The biggest thing is to really spend your time being familiar with them.

In this post, I would focus on topics including linked list manipulation, queue, BFS and summarize some common techniques as before.

 

Question

Given a linked list, in addition to the next pointer, each node has a child pointer that can point to a separate list. With the head node, flatten the list to a single-level linked list.


For instance, the above linked list should be flattened to 1→2->3→4->5->6->7->8->9. The idea is to flatten the linked list by level. Note: this question was asked by Facebook a month ago.

 

Analysis

It’s better to compare this question with Print Binary Tree problem together since both of them are about traversal. In essence, a linked list with two pointers is almost the same as a binary tree.

If you think about the question for a little while, it shouldn’t be hard to realize that this question is exactly the same as print a binary tree by level.

When we need to traverse a tree or graph or any data structure by level, the first thing comes to our mind should be breadth-first search (BFS) and the data structure associated with it is queue. This should be something coming to your mind in less than a second.

So a very straightforward solution can be described like this:

  1. Start from the head node and traverse the linked list following the next pointer.
  2. When a node has a child node, put the child node into the queue.
  3. When the next pointer of the current node is null, pop the queue and repeat from the step 1 using the popped node.

The complexity is linear for both time and space since we only need to traverse or store each node at most once.

 

In-place

For linked list question, sometimes you can do the operation in-place without external storage. Let’s borrow the idea from reversing a linked list. If somehow we could modify the pointer while traversing the linked list, we can flatten the list to single-level without a queue.

Similar to reversing a linked list, we should need two pointers (A, B) that both points to the head initially. The basic idea is to let A keeps moving forward and B is used to locate the first node of next level. So whenever A gets stuck, it will point to the node of next level using B. The flow is like following:

  1. Move A forward (following the next pointer) until the next node is null.
  2. Move B forward until the current node has a child.
  3. Set A’s next pointer to B’s child and clear B’s child pointer (set to null).
  4. Repeat the whole process. You’ll notice that the next time A gets stuck, B will go thru the original path A has gone thru.

I have to say that this solution is a really hard one and I expect that most candidates won’t be able to come up with this. In this solution, the time complexity is still linear (although some nodes will be traversed twice) but space complexity is O(1).

 

Takeaways

  • Traverse by level, BFS and queue go hand in hand. You should spend less than a second to come up with these.
  • Linked list problem sometimes can be solved without external storage. Try to borrow ideas from reverse a linked link problem.
  • I would expect you to spend less than few seconds coming up with the time/space complexity. Otherwise, you need more practice.

The post is written by Gainlo - a platform that allows you to have mock interviews with employees from Google, Amazon etc..

I'd like to learn more

Share on Facebook16Tweet about this on TwitterShare on LinkedIn0Share on Reddit0

9 thoughts on “Flatten a Linked List

    1. Hi Arjun,

      Thanks for the suggestion. As you know, we focus on the idea/thought rather than the answer. I’d recommend readers go and implement by themselves as a practice.

      1. Here is a sample code. I did not write complete Link list implementation for this one. Just the functions that would accomplish this ask. Flattenlist function can be called for head of the list. Helper function gets called for each level.

        void flattenlist(node *head)
        {
        queue q;
        flatlist = new linklist;

        if(head == NULL)
        return;
        q.push(head);
        while(!q.empty())
        {
        node * cur = q.top();
        q.pop();
        helper(cur);
        }
        }

        void helper(node *levelhead)
        {
        while(levelhead!=NULL)
        {
        flatlist->add(levelhead->data);
        if(levelhead->child !=NULL)
        q.push(levelhead->child);
        levelhead = levelhead->next;
        }
        }

        flatlist is a static member of type node* for the class.

  1. When you read the problem, the BFS/queue method hits you right away. The In-place method is quite interesting in the sense that it is not very intuitive! Somewhere in the back of the mind you hear a voice saying “maybe you can use an extra pointer or two and move them ingeniously to get the output” but you are not so sure if it would work. I think in an interview, I’ll go with BFS/queue method first and then later let the interviewer know maybe this can be done in-place but I don’t know the solution off the top of my head 🙂

  2. This is actually not an exact BFS, but rather a modified DFS (with a queue).
    A BFS essentially means that we traverse each level before we traverse the next level.
    However, in this case, we need to go as deep as we can in one path, until it ends and then move to the next level doing exactly the same. I implemented the code for this using recursion.

  3. I, think when solving problems with linked-list, Idea of having two pointers should be a back up approach one should keep in mind, and in-place solution is really a good approach to impress the interviewer, Appreciate jake and team for their effort to help students understand the nuances of approaching the coding interview questions.

    1. Thank you Sumeet. You really got the point that in-place solution is a better approach, although it’s often harder to come up with.

  4. Great break down. Looks the in the place algorithm is correct.

    However, I don’t believe this would work with BFS. Correct me if I’m wrong. An easy way to visualize it is to imagine you picked up the example tree by the root node and let all the nodes dangle. You’ll notice that node 3 and node 5 are on the same level and node 4 would be lower. In the end you would end up with a flattened list of [1,2,3,5,4,6,8,7,9], which is not the order we’re hoping for.

    This can be corrected however by weighting the downward edges with double the weight of the rightward edges. This would then lead us to using Dijkstra’s algorithm. Which would provide a longer run time than the in-place algorithm.

Leave a Reply

Your email address will not be published. Required fields are marked *