Linked List
Linked list is one of the favourite data structures for interview questions. There are dozens of problems with it, from simple exercises to the hard puzzles.
First, you need to learn what is a linked list if you don't know already. Cracking the Coding Interview book has a nice interviews oriented chapter on it. You may also read a relevant chapter in Introduction to Algorithms. Finally, there are hundreds of articles and videos available online, starting from the Wikipedia article.
It's a good exercise to implement a linked list from scratch. How would you do that? How would you perform addition, deletion, or the search of the element? What is the time complexity of each operation?
Problems
Let's solve some problems with the linked list.
The following problem is a simple exercise with the linked list. It's very easy, but it's important to really understand it:
In the following problem you need to reverse the linked list. Unlike with arrays, here it's not that easy...
In the next problem, you need to merge two sorted linked lists. How would you do it?
Finding a cycle
Problems similar to this one are pretty popular with linked lists. Can you solve it without any additional data structures?
Reordering a linked list
Another popular theme for the linked list problems is to somehow rearrange an existing linked list. You may try the following problem:
You may also try the following problem that also asks you to reorder an existing linked list:
More practice problems
Linked list questions are pretty popular, and there are many different ones as well. To be prepared, there is nothing better than solving as many practice problems as possible.
Here are some more nice linked list problems:
