How to solve Linked List Problems ?
Linked List is one of the most common linear data structure on which lot of questions are asked in the interviews. Even though Linked List is simple to understand and implement, many people still get confused about how to solve linked list problems during interview.
In this article, we will see how to solve linked list problems by understanding the common patterns of a linked list problem and going through examples.
1. Rewiring Pointers
In these type of linked list problems, we are asked to modify the linked list according to certain conditions. Even though you may be tempted to try brute force approach on some of these problems, it’s much faster to rewire the pointers and solve the problem.
Example Problems
- Removing a linked list element with given value
- Rotating a singly linked list
- How to delete a node in linked list
2. Use Recursion
Since linked lists are recursive data structures, there are some problems which can be solved easily by writing a recursive function over linked lists.
Example Problems
3. Use Two Pointer Method
In this method, we make two pointers one fast and one slow pointer. In each step, we move slow pointer only once or not at all, and move the fast pointer one or more number of steps at once. This is a very common method especially in problems where we are dealing with sorted lists.
