Top 25 Linked List Coding Interview Questions for Java Programmers

Hello guys, if you are preparing for Software Development interview or want to become a Software Engineer then you must pay full attention to two important topics: first is Data Structure and Algorithms, and second is System Design. These two topics are very essential and you will always find questions from these in any coding interview. They are also the most difficult to crack as they are very vast, no matter how much you will prepare there will be certain questions which you don't know but if you have solid knowledge of fundamental data structure like array, linked list, binary tree, hash table, heap, and graphs as well sorting and searching algorithms like quicksort, merge sort, selection sort, insertion sort, binary tree as well advanced String and graph algorithms then you can still do well.

In the past, I have shared many questions on array, binary tree, hash table and string but not on linked list hence I am going to fill that gap today and share common linked list questions which you can practice to learn one of these important data structure in depth.

If you don't know, along with array, linked list is one of the two fundamental ways to store linear data. In array you store them together in one memory location while linked list allows you to store them on different places in memory. It offer an alternative which is quite important for large data set because you may not always a big chunk of memory to store 1 million records but you may be able to put them if you store them in different places. 

But how does it possible? How are you going to retrieve the data or search if something exists in your data store if its stored in different location inside memory? Well its possible because linked list contains nodes and each node has a data part and an address part which points to the location of next node. 

So basically you search one by one and that's why in worst case you need to search through all nodes if the data you are looking for is stored in last node. Hence, time complexity of search in linked list is O(n) where n is number of nodes. 

At the same time, adding and removing data in linked list is rather easy compared to array as you don't need to shift all the elements to keep them in contiguous memory location. All you need to do here is update a link when you add or remove elements from linked list, hence adding element to head and tail is O(1) in linked list because you store their address inside list. 

Another important quality of linked list data structure is that they are recursive in nature. What does that mean? This means if you take one node form the linked list out then remaining is still a linked list and you can still navigate it the same way you are navigating before. That's the reason you can use recursion to solve many of the linked list problems like reversing a linked list or checking if a linked list is palindrome or not. 

Now its time to look at common linked list questions you can practice to learn more about this data structure but before solving them, I suggest learn to impalement linked list in your favorite programming language like Java. 

While Java API has a LinkedList class you don't need it to solve linked list based problems, instead you can simply create a Node or ListNode class to start with a linked list, if you struggle, see how I implemented linked list in Java, and now it's time for questions

25 Linked list Coding Interview questions for Java Developers

Here is a list of common linked list questions you can solve to get a feel of this data structure:

1. How to Reverse a singly linked list using recursion in Java? (solution)

You will be given a linked list and you need to reverse it using Java programming language, you cannot use any library method which solves this problem but you can use methods form java.lang and java.util package. 

2. Can you write code to Merge two sorted linked lists in Java? (solution)

You will be given two sorted linked list, you need to write a program which accept them and return a new linked containing elements from both linked list. If there are any duplicates then they should be removed from final linked list. 

3. How to remove duplicate elements from linked list in Java? (solution)

Duplicate elements are nodes where data is same in two more more nodes. If linked list contains more than one node with same value then you should remove all additional nodes. The result of your program should be a linked list with unique values.

4. Write a Java Program to Reverse a Linked List without using Recursion?

This is normally a follow up question of first problem where you are asked to solve the same problem using recursion. Once you give recursive solution, interviewer will most likely ask you to convert it into iterative solution. For that you can use Stack data structure which can be used in place of recursion.

5. Write a Java program to reverse every alternate k nodes of a Linked List? (solution)

This one is little bit tough question as you need to reverse every alternate k nodes but you still use two pointer technique to solve this question. 

6. How to find Kth Node from the end of a Linked List in Java? (solution)

7. How to calculate sum of Two Linked Lists using Stacks in Java? (solution)

8. How to perform union of two linked list in Java? (solution)

9. How to implement LRU Cache in Java using linked list? (solution)

10. How will you detect a loop in a linked list and find the node where the loop starts? (solution)

You can solve this linked list coding problem using two pointer pattern. In two pointer pattern, there is a slow and fast pointer, slow pointer moves one node at a time while fast pointer moves two nodes at a time. If a linked list has loop this means they will meet at some point before slow pointer reaches the end of the tail.

 

11. How to convert a sorted Doubly Linked List to Balanced Binary Search Tree in Java? (solution)

12. How to convert a binary tree to doubly linked list in Java? (solution)

13. How to find the middle element of a linked list in single pass in Java? (solution)

You an use two-pointer method to find out the middle element of a linked list in Java. One pointer is called fast pointer which moves two node in each turn and other is called slow pointer which moves one node in each turn. This way when the fast pointer will reach end of the list, slow will be on the middle element. 

14. How to find the Sum of Two Linked Lists using Recursion in Java? (solution)

15. How to find length of a singly linked list? (solution)

You can find length of a linked list by going through all elements of linked list until you find the last element. you can use a variable to track how many element you have visited until you reach to the last element, that's the length of linked list

16. How to find the Sum of Two Linked Lists using Recursion in Java? (solution)

17. Write a Java program to Find intersection of two Linked Lists? (solution)

18. How to Find intersection of two Linked Lists - O(m + n) Time Complexity and O(1) Space Complexity in Java? (solution)

19. Write a Java program to find maximum element from each sub-array of size 'k'? (solution)

20. What is difference between an ArrayList and LinkedList in Java? (answer)

ArrayList and LinkedList are two Java classes which represent array and linked list data structure. ArrayList is backed by array but it represent a dynamic array, I mean it can resize itself. ArrayList provide fast access using index but search is slow in LinkedList as you need to traverse through the list. 

21. What is difference between an array and linked list data structure? (answer)

There are many difference between these two data structure but the most important one is how they store data. For example, array store data in contiguous location while linked list can store data in any way like in continuous or scattered because here the address of next node is stored in the previous node. 

22. What is time complexity of adding and removing a node from head and tail in linked list? (answer)

Adding and removing elements from head or tail is easy in linked list and they are O(1) operation because all you need to do is change the pointers. They are not dependent upon how many elements your linked list contains hence they are O(1) operation or constant time operation and will take same time irrespective of how small or a big a linked list is.

23. What is difference between singly and doubly linked list in Java? (answer)

Main difference between them is that singly linked only allows you to traverse in one direction, forward or reverse but double linked list allows you to traverse in both directions, forward and backward, as it contains two pointers. Which means you can go to previous or next node from doubly linked list which is not possible in case of singly linked list. 

24. Can linked list contain duplicate element? (answer)

Yes, linked list may contain duplicates. Unlike Set data structure, the linked list data structure doesn't prevent you from storing duplicates. 

25. How much time it take to find a given value in a singly linked list? (answer)

It takes O(n) time to find a given value in linked list because you need to search through each node in worst case. 

5 Things Programmer should remember about Linked List

Now let's revise the things every programmer should know and remember about linked list data structure:

1. linked list is a recursive data structure which means you can use recursion to solve linked list problems. 

2. For search, time complexity is O(n) in linked list where n is number of nodes

3. For traversing in one pass, you can use two pointer algorithms to keep reference of fast and slowing moving pointers. 

4. Linked List is ideal data structure for adding and removing data as performance is O(1) if you want to add and remove from head or tail

5. Linked List provides an alternate way to store data than array and its very space efficient. 

That's all about the common linked list problem for practice, most of the question I have already solved and you can find them on my blogs but if you struggle to any questions, just ping me and I can post a solution. Also, if you got any other interesting linked list questions then feel free to share with us in comments. 

Do remember all the tips I have shared about linked list they will help you to solve these questions, particularly recursion. One more thing, if recursion is not allowed then you can use a recursive data structure like Stack to replace the recursion and convert a recursive solution to iterative one. 

Other Programming Articles you may like

• 15 Recursion exercise for Java Programmers (recursion)
• How to check if a given number is prime or not? (solution)
• 10 Dynamic Programming problems for interviews (dynamic programming)
• How to print factorial of a given number in Java? (factorial)
• 75 Programming Questions for Interviews (questions)
• How to find if the given String is a palindrome in Java? (solution)
• How to reverse String in Java without using StringBuffer? (solution)
• How to reverse an int variable in Java? (solution)
• 100+ Data Structure and Algorithms problems for interviews (questions)
• How to find a missing number in a sorted array? (solution)
• 10 Matrix based coding problems (matrix problems)
• 10 Free Courses to learn Java Programming (free courses)
• Write a program to check if a number is a power of two or not? (solution)
• 30 System Design Problems for Interviews (system design problems)
• 10 Free Courses to learn Data Structure and Algorithms (free courses)
• How do you reverse the word of a sentence in Java? (solution)
• How do you swap two integers without using a temporary variable? (solution)

Thanks, for reading this article so far, if you like this linked list coding problems, for interviews then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note. 

P. S. - If you are new to Computer Science and DSA and looking for a free online course to level up your DSA skills then I highly recommend you to check out these free data structure and algorithms courses from Udemy and Courses. It's completely free and more than 1 million students have already joined this course. It also contains courses in different programming language like Java, Python,  C, and C++.