Linked list scenario based questions

1. Question 1. How To Find Middle Element Of A Singly Linked List In One Pass?

   Answer :

   You should clarify what does mean by one pass in this question. If Interviewer says that you cannot loop twice and you just have to use one loop, then you can use the two pointer approach to solving this problem. In the two pointer approach, you have two pointers, fast and slow. In each step, the fast pointer moves two nodes, while slow pointer just steps one node. So, when fast pointer will point to the last node i.e. where next node is null, the slow pointer will be pointing to the middle node of the linked list.

2. Question 2. How To Check If Linked List Contains Loop In Java? How To Find The Starting Node Of The Loop?

   Answer :

   This is another interesting linked list problem which can be solved using the two pointer approach discussed in the first question. This is also known as tortoise and hare algorithm. Basically, you have two pointers fast and slow and they move with different speed i.e. fast moves 2 notes in each iteration and slow moves one node. If linked list contains cycle then at some point in time, both fast and slow pointer will meet and point to the same node, if this didn't happen and one of the pointer reaches the end of linked list means linked list doesn't contain any loop.

C++ Interview Questions

3. Question 3. How To Reverse A Linked List In Java?

   Answer :

   This is probably the most popular linked list interview question, which is asked to both junior programmers with 2 to 3 years of experience and senior developers containing 4 to 6 years of experience. Some of you may think this is the simplest of linked list problem but when you actually go doing it, you will be stuck and many places. The simplest approach to solving this problem is by using recursion because linked list is a recursive data structure as shown in the solution article.

4. Question 4. How To Reverse A Singly Linked List Without Recursion In Java?

   Answer :

   The previously linked list interview question becomes even more challenging when the interviewer asked you to solve the problem without recursion. you need to keep reversing links on the node until you reach the end, which will then become new head.

C++ Tutorial

5. Question 5. How Would You Remove A Node From A Doubly Linked List?

   Answer :

   This is one of the frequently asked linked list interview questions, mostly asked freshers and computer science college graduates. In order to remove a node from the doubly linked list, you need to go through that node and then change the links so that it points to the next node. Removing nodes from head and tail is easy in linked list but removing a node from the middle of the linked list requires you to travel to the node hence take O[n] time. If you want to learn more about basic operations on linked list data structure, please read a good book on Data Structure and Algorithms e.g. Introduction to Algorithms by Thomas H. Carmen.

Data Warehousing Interview Questions

6. Question 6. Write A Program To Convert A Binary Tree Into A Doubly Linked List?

   Answer :

   This problem is opposite of question 25 where you need to write a program to convert a double linked list to the balanced binary tree. The left and right pointers in nodes of a binary tree will be used as previous and next pointers respectively in converted doubly linked list. The order of nodes in the doubly linked list must be same as Inorder of the given Binary Tree. The first node of Inorder traversal [left most node in the binary tree] must be the head node of the doubly linked list.

7. Question 7. How To Remove Duplicate Nodes In An Unsorted Linked List?

   Answer :

   This problem is similar earlier problems related to String and arrays i.e. removing duplicate elements in an array [see] or removing duplicate characters from given String [see here]. You need to write a program to remove all duplicate nodes from an unsorted linked list in Java. For example if the linked list is 22->21->22->31->41->23->21 then your program should convert the list to 22->21->31->41->23. This question is also given in the famous Cracking the Coding Interview book so you can look at their solution as well.

Data Warehousing Tutorial Data Structures Interview Questions

8. Question 8. How To Find The Length Of A Singly Linked List In Java?

   Answer :

   This is one of the easiest linked list questions you can expect in an interview. That's why it is often asked on telephonic interviews. In order to find the length of linked list, you can iterate over linked list and keep a count of nodes until you reach the end of the linked list where next node will be null. The value of the counter is the length of linked list.

9. Question 9. Write Code To Print Out The Data Stored In Each Node In A Singly Linked List?

   Answer :

   This is another simplest question which just tests whether you know linked list traversal or not. You can get the value from the node by accessing its value property, you just need to traverse through linked list, access each node and print value.

Computer Science Engineering Interview Questions

10. Question 10. Write A Program To Print A Linked List In Reverse Order? E.g. Print Linked List From Tail To Head?

    Answer :

    You can print nodes of linked list in reverse order by using Stack data structure in two steps:

    Step 1: Traverse the linked list from the head and put the value of each node into Stack until you reach the last node. This will take O[n] time.

    Step 2: Pop the elements out from the stack and print. This will take O[1] time.

    Input: 1->2->3

    Output: 3 2 1

Data Structures Tutorial

11. Question 11. How To Find The Kith Node From The End In A Singly Linked List?

    Answer :

    • This is one of the tricky but frequently asked linked list questions. Some of you may be wondering how do you find kth node from end, singly linked list can only traverse in one direction and that is forward then how do you count nodes from the end.
    • Well, you don't have to, you can still move forward and count nodes from the end? Actually, that's the trick. You can use two pointers to find the Nth node from the end in a singly linked list. They are known as fast and slow points.
    • You start slow pointer when the fast pointer reaches to the Kth node from start e.g. if you have to find 3rdnode from the end then you start slow pointer when the fast pointer reaches to the 3rd node. This way, when your fast pointer reaches to the end, your slow pointer will be on the 3rd node from the end.
C & Data Structures Interview Questions

12. Question 12. How To Delete Alternate Nodes Of A Linked List?

    Answer :

    You are given a Singly Linked List. Starting from the second node delete all alternate nodes of it. For example, if the given linked list is 1->4->8->10->15 then your function should convert it to 1->8->15.

C++ Interview Questions

13. Question 13. What Is The Difference Between An Array And Linked List In Java?

    Answer :

    This is one of the frequently asked linked list questions on programming job interviews. There is much difference between an array and linked list but the most important is how they are stored into the memory location. Array stores elements at the adjacent memory location, while linked list stores them at scattered, which means searching is easy in an array and difficult in linked list but adding and removing an element from start and end is easy in linked list. See here for more differences between array and linked list.

Data Structure & Algorithms Tutorial

14. Question 14. Difference Between Singly And Doubly Linked List In Java?

    Answer :

    The key difference between a single and double linked list data structure in java is that singly linked list only contains pointer to next node, which means you can only traverse in one direction i.e. forward, but doubly linked list contains two points, both previous and next nodes, hence you can traverse to both forward and backward direction.

15. Question 15. How To Implement A Linked List Using Generics In Java?

    Answer :

    It's not easy to implement a linked using generics in Java, especially if have not written any parametric or generic class, but it's a good exercise to get familiar with both linked list data structure as well generics in Java.

Data Structure & Algorithms Interview Questions

16. Question 16. How To Insert A Node At The Beginning Of The List?

    Answer :

    Inserting a node at the beginning of the list is probably the easiest of all operations. Lets talk about what is involved here referring to the diagram above. This involves creating a new node [with the new data, say int 10], making its link point to the current first node pointed to by head [data value 2] and lasting changing head to point to this new node. Simple, right.

17. Question 17. How To Insert A Node At The End Of The List?

    Answer :

    This case is a little bit more evolved. If you have a tail pointer, it is as easy as inserting at the beginning of the list. If you do not have a tail pointer, you will have to create the new node, traverse the list till you reach the end [i.e. the next pointer is NULL] and then make that last nodes next pointer point to the new node.

Advanced C# Interview Questions

18. Question 18. How Do You Traverse A Linked List In Java?

    Answer :

    There are multiple ways to traverse a linked list in Java e.g. you can use traditional for, while, or do-while loop and go through the linked list until you reach the end of the linked list. Alternatively, you can use enhanced for loop of Java 1.5 or Iterator to traverse through a linked list in Java. From JDK 8 onwards, you can also use java.util.stream.Stream for traversing a linked list.

Data Warehousing Interview Questions

19. Question 19. How Do You Find The Sum Of Two Linked List Using Stack In Java?

    Answer :

    This is a relatively difficult linked questions when you compare this to reversing a linked list or adding/removing elements from the linked list. In order to calculate the sum of linked list, you calculate the sum of values held at nodes in the same position, for example, you add values at first node on both the linked list to find the first node of resultant linked list. If the length of both linked list is not same then you only add elements from shorter linked list and just copy values for remaining nodes from the long list.

20. Question 20. How Do You Convert A Sorted Doubly Linked List To A Balanced Binary Search Tree In Java?

    Answer :

    This is one of the difficult linked list questions you will find on interviews. You need to write a program to convert a given doubly Linked, which is sorted in ascending order to construct a Balanced Binary Search Tree which has same the values as the given doubly linked list. The challenge is usually increased by putting a restriction to construct the BST in-place i.e. no new node should be allocated for tree conversion]

    Input: A Doubly linked list 10 20 30 40 50 60 70

    Output: A balanced binary search tree BST

    40

    /

    20 60

    / /

    10 30 40 70

Advanced C++ Interview Questions

21. Question 21. How Do You Calculate The Sum Of Two Linked List Using Recursion In Java?

    Answer :

    This is another interesting linked list based algorithm question for Java programmers. You cannot use the java.util.LinkdList class but you have to write your own linked list implementation in Java to solve this problem.

22. Question 22. How To Implement Lru Cache In Java Using Linked List?

    Answer :

    An LRU cache is the cache where you remove least recently used an element when the cache is full or about to fill. It's relatively easy in Java if you are allowed to use one of the Collection class e.g. you can use a LinkedHashMap to implement LRU cache in Java, but you should also prepare how you can use a doubly linked list to create an LRU cache.

23. Question 23. How Do You Reverse Every Alternate K Nodes Of A Linked List In Java?

    Answer :

    This is another difficult linked list algorithm question which is mostly asked to experienced programmers e.g. programmer having 3 to 6 years of experience. You have been given a singly linked list and you need to write a function to reverse every alternate k nodes [where k is an input to the function] in an efficient way. You also need to calculate the time and space complexity of your algorithm.

    Example:

    Inputs: 1->2->3->4->5->6->7->8->9->NULL and k = 3

    Output: 3->2->1->4->5->6->9->8->7->NULL.

C and C++ Interview Questions

24. Question 24. How Do Add Two Numbers Represented Using Linked List In Java?

    Answer :

    You have given two numbers represented by two linked lists, write a function that returns the sum of these two lists. The sum list is linked list representation of addition of two input numbers. There are two restrictions to solve this problem i.e. you cannot modify the lists and you are not allowed to use explicit extra space. You can use recursion to solve this problem.

    Input:

    First List: 1->2->3 // represents number 123

    Second List: 9->9->9 // represents number 999

    Output:

    Resultant list: 1->1->2->2 // represents number 1122

    That's all about some of the frequently asked linked list based coding questions from Programming Interviews. As I said, linked list is one of the essential data structure and you should have a good command over it, especially if you are preparing for Google or Amazon job interview. Once you solve these problems, you can try solving questions given in Algorithm Design Manual by Steven S. Skiena. They are tougher but can really improve your data structure and algorithm skills.

Data Structures Interview Questions

25. Question 25. What Is A Linked List?

    Answer :

    Linked list is an ordered set of data elements, each containing a link to its successor [and typically its predecessor].

26. Question 26. How Many Pointers Are Required To Implement A Simple Linked List?

    Answer :

    You can find generally 3 pointers engaged:

    1. A head pointer, pointing to the start of the record.
    2. A tail pointer, pointing on the last node of the list. The key property in the last node is that its subsequent pointer points to nothing at all [NULL].
    3. A pointer in every node, pointing to the next node element.

27. Question 27. How Many Types Of Linked Lists Are There?

    Answer :

    Singly linked list, doubly linked list, multiply linked list, Circular Linked list.

Computer Science Engineering Interview Questions

28. Question 28. How To Represent A Linked List Node?

    Answer :

    The simplest representation of a linked list node is wrapping the data and the link using a typedef structure and giving the structure as a Node pointer that points to the next node. An example representation in C is

    /*ll stands for linked list*/

    typedef struct ll

    {

    int data;

    struct ll *next;

    } Node;

29. Question 29. Describe The Steps To Insert Data At The Starting Of A Singly Linked List?

    Answer :

    Inserting data at the beginning of the linked list involves creation of a new node, inserting the new node by assigning the head pointer to the new node next pointer and updating the head pointer to the point the new node. Consider inserting a temp node to the first of list

    Node *head;

    void InsertNodeAtFront[int data]

    {

    /* 1. create the new node*/

    Node *temp = new Node;

    temp->data = data;

    /* 2. insert it at the first position*/

    temp->next = head;

    /* 3. update the head to point to this new node*/

    head = temp;

    }

30. Question 30. How To Insert A Node At The End Of Linked List?

    Answer :

    This case is a little bit more complicated. It depends on your implementation. If you have a tail pointer, its simple. In case you do not have a tail pointer, you will have to traverse the list till you reach the end [i.e. the next pointer is NULL], then create a new node and make that last nodes next pointer point to the new node.

    void InsertNodeAtEnd[int data]

    {

    /* 1. create the new node*/

    Node *temp = new Node;

    temp->data = data;

    temp->next = NULL;

    /* check if the list is empty*/

    if [head == NULL]

    {

    head = temp;

    return;

    }

    else

    {

    /* 2. traverse the list till the end */

    Node *traveller = head;

    while [traveler->next != NULL]

    traveler = traveler->next;

    /* 3. update the last node to point to this new node */

    traveler->next = temp;

    }

    }

31. Question 31. How To Insert A Node In Random Location In The List?

    Answer :

    As above, youd initial produce the new node. Currently if the position is one or the list is empty, youd insert it initially position. Otherwise, youd traverse the list until either you reach the specified position or the list ends. Then youd insert this new node. Inserting within the middle is that the difficult case as you have got to make sure you do the pointer assignment within the correct order. First, youd set the new nodes next pointer to the node before that the new node is being inserted. Then youd set the node to the position to purpose to the new node. Review the code below to get an idea.

    void InsertNode[int data, int position]

    {

    /* 1. create the new node */

    Node *temp = new Node;

    temp->data = data;

    temp->next = NULL;

    /* check if the position to insert is first or the list is empty */

    if [[position == 1] || [head == NULL]]

    {

    // set the new node to point to head

    // as the list may not be empty

    temp->next = head;

    // point head to the first node now

    head = temp;

    return;

    }

    else

    {

    /* 2. traverse to the desired position */

    Node *t = head;

    int currPos = 2;

    while [[currPos < position] && [t->next != NULL]]

    {

    t = t->next;

    currPos++;

    }

    /* 3. now we are at the desired location */

    /* 4 first set the pointer for the new node */

    temp->next = t->next;

    /* 5 now set the previous node pointer */

    t->next = temp;

    }

    }

32. Question 32. How To Delete A Node From Linked List?

    Answer :

    • The following are the steps to delete node from the list at the specified position.
    • Set the head to point to the node that head is pointing to.
    • Traverse to the desired position or till the list ends; whichever comes first
    • You have to point the previous node to the next node.

33. Question 33. How To Reverse A Singly Linked List?

    Answer :

    • First, set a pointer [*current] to point to the first node i.e. current=head.
    • Move ahead until current!=null [till the end]
    • set another pointer [*next] to point to the next node i.e. next=current->next
    • store reference of *next in a temporary variable [*result] i.e. current->next=result
    • swap the result value with current i.e. result=current
    • And now swap the current value with next. i.e. current=next
    • return result and repeat from step 2
    • A linked list can also be reversed using recursion which eliminates the use of a temporary variable.
C & Data Structures Interview Questions

34. Question 34. Compare Linked Lists And Dynamic Arrays?

    Answer :

    • A dynamic array is a data structure that allocates all elements contiguously in memory, and keeps a count of the present number of elements. If the area reserved for the dynamic array is exceeded, its reallocated and traced, a costly operation.
    • Linked lists have many benefits over dynamic arrays. Insertion or deletion of an element at a specific point of a list, is a constant-time operation, whereas insertion in a dynamic array at random locations would require moving half the elements on the average, and all the elements in the worst case.
    • Whereas one can delete an element from an array in constant time by somehow marking its slot as vacant, this causes fragmentation that impedes the performance of iteration.

35. Question 35. What Is A Circular Linked List?

    Answer :

    In the last node of a singly linear list, the link field often contains a null reference. A less common convention is to make the last node to point to the first node of the list; in this case the list is said to be circular or circularly linked.

36. Question 36. What Is The Difference Between Singly And Doubly Linked Lists?

    Answer :

    A doubly linked list whose nodes contain three fields: an integer value and two links to other nodes one to point to the previous node and other to point to the next node. Whereas a singly linked list contains points only to the next node.

Data Structure & Algorithms Interview Questions

37. Question 37. What Are The Applications That Use Linked Lists?

    Answer :

    Both stacks and queues are often implemented using linked lists, other applications are skip list, binary tree, unrolled linked list, hash table, heap, self-organizing list.

38. Question 38. How To Remove Loops In A Linked List [or] What Are Fast And Slow Pointers Used For?

    Answer :

    The best solution runs in O[N] time and uses O[1] space. This method uses two pointers [one slow pointer and one fast pointer]. The slow pointer traverses one node at a time, while the fast pointer traverses twice as fast as the first one. If the linked list has loop in it, eventually the fast and slow pointer will be at the same node. On the other hand, if the list has no loop, obviously the fast pointer will reach the end of list before the slow pointer does. Hence we detect a loop.

39. Question 39. What Will You Prefer To Use A Singly Or A Doubly Linked Lists For Traversing Through A List Of Elements?

    Answer :

    Double-linked lists require more space per node than singly liked lists, and their elementary operations such as insertion, deletion are more expensive; but they are often easier to manipulate because they allow fast and easy sequential access to the list in both directions. On the other hand, doubly linked lists cannot be used as persistent data structures. So, for traversing through a list of node, doubly linked list would be a better choice.

Linked List Related Tutorials

Linked List Related Interview Questions

Linked List Related Practice Tests