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.
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.
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:
- Start from the head node and traverse the linked list following the next pointer.
- When a node has a child node, put the child node into the queue.
- 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.
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:
- Move A forward (following the next pointer) until the next node is null.
- Move B forward until the current node has a child.
- Set A’s next pointer to B’s child and clear B’s child pointer (set to null).
- 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).
- 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.