Linked List Interview Questions

Applications Of Linked List

Linked lists, as discussed above, are very elementary data structures. They are used in multiple applications.

Applications of a linked list are

• In music applications, the playlists can be played from the beginning and skipped to the next. Such applications used linked lists to implement this feature.
   
• In applications where we can view pictures and videos, we can move to the following image or video one by one. Here also, linked lists are used.
   
• Allocation of dynamic memory: Linked lists allow dynamic allocation of memory as new nodes can be created. New nodes can be added to any place in the linked list by changing only a few pointers in the nodes.
   
• Solving polynomials: Solving a mathematical polynomial is a task that can be handled in linked lists very quickly. The nodes can be considered as powers in the polynomial, and the values of nodes as the coefficients of those powers.
   
• Implementation of other data structures: Stacks, queues, and arrays can be implemented using linked lists. Also, linked lists can implement an adjacency list to represent graphs.

 

Let's visit some questions you might be asked on linked lists in an interview. Here are the questions sorted based on their difficulty.

Linked List Interview Questions for Freshers

Here we will discuss the easy-level linked list of interview questions you might get asked in an interview.

Q1. What are the types of linked lists?

Linked lists are of 4 kinds, namely.

• Singly-linked lists
• Doubly-linked lists
• Multiple-linked lists
• Circular-linked lists.

Q2. What is a doubly linked list?

Doubly linked lists are linked lists where a node points to both the node ahead of it and behind it. A node in a doubly-linked list has two pointers and can traverse in both directions.

Q3. How many pointers are present in a singly-linked list?

In a singly linked list, each node has only one pointer assigned to it. The pointer points to the node next to it, creating a chain of nodes. The last node point to NULL to end the linked list. 

Q4. What type of memory allocation is done in a linked list?

Dynamic memory allocation is done in a linked list. The nodes are created and deleted from the linked list when the need to do so arises. 

Q5. How will you find the middle element of a linked list in a single pass?

To find the middle of a linked list in a single pass

• Create two-pointers.
• Initialise both the pointers to the head of the linked list. 
• Make one pointer move two nodes simultaneously and the other only one node. 
• Once the pointer moving two nodes at a time reaches the end of the linked list, the pointer moving a single node at a time will be pointing at the middle node.

Q6. Insert a node at the end of a linked list.

To insert a node at the end of a linked list

• First, create the node which needs to be inserted and make it a point to NULL.
• Create a pointer, which initially points at the head of the linked list.
• Traverse the linked list using the pointer till you reach the node pointing to NULL.
• Make the last node point to the node created in the first step.

Q7. What is a circular linked list?

A circular linked list is a linked list in which the tail of the linked list points to the head of the linked list. In a circular linked list, there is no such start and end of a linked list. We assume a node is the head of the list and the node before it is the tail.

Q8. What is a singly-linked list?

A singly linked list is a collection of nodes with a single pointer—the pointer of the nodes in a singly linked list points towards the node next to it. 

Q9. Remove duplicates from a linked list that is sorted.

To remove duplicates from a sorted linked list, follow the steps below.

• First, create two pointers, initialised with the head of the linked list.
   
• Move one of the pointers till the values of both pointers are different.
   
• Once different value pointers are found, make the next of the first pointer the second pointer.
   
• Move the first pointer to the next node, and continue this process, till all nodes are covered.

Q10. Implement a node for a singly linked list in C++.

Here is an implementation of a node in the linked list.

Here we have created a struct which contains an integral value and a pointer. This struct is a node for a linked list.

struct SinglyLinkedList{
      // stores the value in node
	  int value;
      // stores the next node
	  node *next;
};

 

Also Read - Operations on linked lists in C/C++

Linked List Interview Questions For Intermediate

This section contains a medium-level linked list of interview questions that you might get asked in an interview.

Q11. Delete the middle node in a singly linked list.

In this code, we are taking two-pointers. One is moving two nodes at a time, and the other is one node.

In the above diagram, it is shown how a node is removed.

In the code below we count the number of nodes in the linked list. After that we divide the count by 2. Then we traverse to the node behind the middle node with the help of counter. We simply perform a deletion on reaching the desired node.

SinglyLinkedList* deleteMiddleNode(SinglyLinkedList *head){
	  SinglyLinkedList *current;
      if( head->next == nullptr ){
        return nullptr;
      }
      int count = 0;
      current = head;
      // Counting number of nodes in the linked list
      while( current != nullptr){
          count++;
          current = current->next;
      }
      current = head;
      count = count/2 - 1;
      // Going to the middle node by halving total count
      while(count != 0){
          count--;
          current = current->next;
      }
      // Deletion of node
      current->next = current->next->next;
      return head;
}

Q12. Detect loop in the singly linked list.

All the visited linked lists are stored in an array to detect a loop in the linked list. We store all the visited nodes in a vector. We then compare whether the current node is present or not  in the vector. If the node is present in the vector, a loop is detected.

bool has_cycle(SinglyLinkedListNode* root) {
    
    // vector to store nodes of linked list
    vector<SinglyLinkedListNode*> nodes; 
    
    // node to iterate over the linked list
    SinglyLinkedListNode* node = root;
    
    // run till we don't reach the end of linked list
    while( node->next != nullptr ){
    // Detecting whether the current node is already in the vector
        for( int i =    0 ; i < nodes.size() ; i++ ){
            
            // if we find the current node in the vector
            // storing the linked list nodes we will return a yes
            if( nodes[i] == node ){
                return 1;
            }
        }
        // push the node into the vector
        nodes.push_back(node);
        
        // move to the next node
        node = node->next;
    }
    
    // since we have reached the end of the list
    // there will be no loop in the linked list
    return  0;
}

Q13. Merge two linked lists into a single linked list.

The linked lists are assumed to need to be sorted. So we can go to the tail of one of the lists and point it to the head of the second linked list.

In the above diagram it is shown how 2 linked lists are merged.

SinglyLinkedList* merge_lists(SinglyLinkedList* head1,SinglyLinkedList* head2){
    SinglyLinkedList* current = head1;
    
    // Taking the current pointer to the last node of first linked list
    while( current->next != nullptr ){
        current = current->next;
    }
    
    // Connecting the tail of first linked list to head of second linked list
    current->next = head2;
    return head1;
}

Q14. Find the length of loop in a singly linked list.

This question is a continuation of the problem “detect a loop in a linked list”. once we find that there exists a loop in the list, we need to just iterate from the starting node of the loop till it doesn't reach itself again. to get a better grasp over the problem visit the blog on “Find the length of loop in linked list”.

Q15. Insert a node at the start of a singly linked list.

In this, we are just adding a node to the head and making the new node the new head.

The above diagram, it is shown how a new node is inserted at the start of a linked list.

void insert(SinglyLinkedList* head,SinglyLinkedList* newNode){
    if( newNode == nullptr ){
        return nullptr;
    }
    SinglyLinkedList *current = head;
    // Assigning new head as the new node
    head = newNode;
    // Connecting the new head to the previous head
    newNode->next = current;
}

Q16. Insert a node in the 5th position in a singly linked list.

In this first, we are traversing to the fourth node. Then we are pointing the new nodes next towards the start of the fifth node and the fourth node's next as the new node.

void insertNodeAtPosition(SinglyLinkedListNode* head,SinglyLinkedListNode* temp,int position){
    SinglyLinkedListNode *current = head;
    // Here we are making the pointer point at the 4th node
    int count  = position-1;
    while( count-- && current != nullptr ){
        current = current->next;
    }
  	// Node is being inserted at correct place
  	if(current != nullptr && current->next != nullptr){
        temp->next = current->next;
        current->next = temp;
    }
}

Q17. Reverse alternate nodes in a singly linked list.

What we need to do is reverse the nodes at alternate positions. In the diagram below, it is shown how the alternate nodes are being reversed. 

The intuitive approach that strikes one's mind is that make two seperate list by deleting the alternate nodes from the given linked list. So we'll be having a linked lists where alternate nodes would be deleted and a linked list with alternate nodes. Now reverse the linked list with alternate nodes and append it at the end of original list. We'll be getting the desired linked list. To gain more insights into the problem try the problem by yourself  

Q18. Remove a node from the start of the singly linked list.

To remove a node from the start, we will point the first node towards the null and make the second node the head of the linked list.

SinglyLinkedList* remove_start(SinglyLinkedList* head){
	if(head == nullptr) 
		return head;
	
	// delete the starting node	
    head = head->next;
    
    // Returning new head
    return head;
}

Q19. Remove a node from the 10th position in a linked list.

First, to remove a node from the 10th position in a linked list, traverse to the 9th node. Assign the next of the 9th node as the 11th node, and the 10th node will be removed.

void delete(SinglyLinkedListNode* head,int position){
    SinglyLinkedListNode *current = head;
    // Here we are making the pointer point at the 9th node
    int count  = position-1;
    while( count-- && current != nullptr ){
        current = current->next;
    }
  	// Node is being deleted at 10th place
  	if(current != nullptr && current->next != nullptr && current->next->next != nullptr){
        current->next = current->next->next;
    }
}

Q20. Remove a node from the end of a linked list.

To remove a node from the end of a linked list, traverse to the second last node in the linked list. Then make the second last node point at null.

void deleteNodeAtEnd(SinglyLinkedList* head){
    if( head == nullptr ){
        return nullptr;
    } 
    SinglyLinkedList *current = head;
    // Going to the second last node of the linked list
    while( current->next != nullptr && current->next->next != nullptr){
        current = current->next;
    }
    // Deleting the last node
    current->next = nullptr;
}

 

Must Read: Spark Interview Questions

Linked List Interview Questions for Experienced

Q21. Why is merge sort better than quicksort in a singly linked list?

In case of arrays, we have O(1) random access to any element while implementing any sorting algorithm. It's because of the contiguous memory allocation in arrays. Whereas this is not the case with singly linked lists. Random access is certainly not O(1), as we'll have to travel from head to the pivot element as per quick sort algorithm. This is will lead to an overhead leading to increased time complexity. Hence merge-sort works better than quick sort in a singly linked list. 

Q22. Reverse a linked list.

To reverse a linked list, take 3-pointers. The third pointer will be at the next of the second pointer, and the first pointer at the next of the second. Every time to reverse a node, make the next of the second pointer as first. After reversing a node, shift the pointers to the right by reassigning the first as the second and the second as the third pointer.

In the above diagram it is shown how the linked list is reversed.

SinglyLinkedList* reverse_list(SinglyLinkedList* head){
    if( head == nullptr ){
        return nullptr;
    }
    SinglyLinkedList *previous = head,*current = head->next,*next;
    // Reversing the nodes using 3 pointers while traversing
    while( current != nullptr){
        next = current->next;
        current->next = previous;
        previous = current;
        current = next;
    }
    head->next = nullptr;
    // Assigning new head
    head = previous;
    return head;
}

 

Practice reverse linked list problems for better understanding

Q23. Sort a linked list containing 0's, 1's, and 2's in a single pass.

To sort, create three lists, one for 0s, one for 1s and one for 2s. After that, connect the end of 0s to the end of 1s and the end of 1s to the end of 2s to sort the linked list.

In the above diagram it is shown how the linked list containing 0s,1s and 2s are sorted.

SinglyLinkedList* sort012(SinglyLinkedList* head){
    SinglyLinkedList *newHead,*pointer_of_1 = nullptr,*pointer_of_2 = nullptr,*pointer_of_3 = nullptr,*head_of_1,*head_of_2,*head_of_3,*current;
    current = head;
    head_of_1 = nullptr;
    head_of_2 = nullptr;
    head_of_3 = nullptr;
    while(current != nullptr){
        // Creating a linked list all 0s
        if( current->data == 0 ){
            if( pointer_of_1 == nullptr ){
                pointer_of_1 = current;
                head_of_1 = current;
            }
            else{
                pointer_of_1->next = current;
                pointer_of_1 = pointer_of_1->next;
            }
        }
        // Creating a linked list all 1s
        else if( current->data == 1 ){
            if( pointer_of_2 == nullptr ){
                pointer_of_2 = current;
                head_of_2 = current;
            }
            else{
                pointer_of_2->next = current;
                pointer_of_2 = pointer_of_2->next;
            }
        }
        // Creating a linked list all 2s
        else{
            if( pointer_of_3 == nullptr ){
                pointer_of_3 = current;
                head_of_3 = current;
            }
            else{
                pointer_of_3->next = current;
                pointer_of_3 = pointer_of_3->next;
            }
        }
        current = current->next;
    }
    // Merging the linked lists of 0s, 1s and 2s by handling all edge cases
    if( head_of_1 != nullptr ){
        newHead = head_of_1;
        if( pointer_of_1 != nullptr ){
            pointer_of_1->next = head_of_2;
            if( pointer_of_2 != nullptr ){
                pointer_of_2->next = nullptr;
            }
        }
        if( pointer_of_2 != nullptr ){
            pointer_of_2->next = head_of_3;
            if( pointer_of_3 != nullptr ){
                pointer_of_3->next = nullptr;
            }
        }
    }
    else if( head_of_2 != nullptr ){
        newHead = head_of_2;
        if( pointer_of_2 != nullptr ){
            pointer_of_2->next = head_of_3;
            if( pointer_of_3 != nullptr ){
                pointer_of_3->next = nullptr;
            }
        }
    }
    else{
        newHead = head_of_3;
        if( pointer_of_3 != nullptr ){
            pointer_of_3->next = nullptr;
        }
    }
    return newHead;
}

Q24. Implement a stack using a linked list.

You must implement push and pop operations to implement a stack using a linked list.

The push operation adds a new node at the end of the linked list, and the pop operation removes the linked list's tail. The push operation can be done in O(1) time complexity by keeping a pointer at the tail, and the pop will take O(n) time complexity as there is no way for the tail pointer to go back after deletion. 

Q25. Implement a queue using a linked list.

To implement a queue using a linked list, you need to implement the push and pop operations.

The push operation adds a new node at the tail, and the pop operation removal the head of the linked list. The push operation can be done in O(1) time complexity by keeping a pointer at the tail, and the pop will also take O(1) time complexity by keeping a pointer at the head.

Q26. Make the tail of a linked list it's head.

To make the tail of a linked list its head, go through the following steps.

• First, take, and create two pointers, one pointing at the head and another pointing to the next of the head.
• Traverse the pointer till the farther pointer reaches the tail.
• Make the tail pointer point to the head of the linked list and the one before the tail null. 

Q27. Check the linked list for palindrome.

To check for the palindrome, we store all the nodes in a stack. Now we can traverse the linked list and check if the value of node at the same position from the end matches the current node's value. Below is an implementation of the same.  

bool isPalindrome(SinglyLinkedList* head) {
		// if head is null then return true 
        if(head==nullptr) return true;
        
        // create a stack to check for nodes in the reverse direction
        stack<SinglyLinkedList*> st;
        
        //node for traversing the linked list 
        SinglyLinkedList* node = head;
        
        // push all nodes in the stack
        while(node!=nullptr){
            st.push(node);
            node = node->next;
        }
        
        // reinitialise node pointer to again traverse the linked list
        node = head;
        
        // till the stack is not empty check if stack top element's value
        // is same as current linked list node value. 
        while(!st.empty()){
        
        	// if values are not same return false right away
            if(st.top()->data != node->data){
                return false;
            }
            
            // pop the node from the stack
            st.pop();
            
            // move to the next node
            node = node->next;
        }
        
        return true;
}

Q28. Merge two sorted linked lists from the end.

To merge two linked lists from the end, perform the following operations

• First, take a pointer named "temporary" and initialize it with NULL.
• Then traverse both the linked lists and choose the node of the one with a smaller value.
• Make the node point towards "temporary", and assign a head to the node.
• Continue this process till all the nodes have been included in the new list whose first node is pointed by "temporary".

In this manner, you will get two linked lists merged from the end, whose head is pointed by "temporary".

SinglyLinkedList* reverse_merge(SinglyLinkedList *head1,SinglyLinkedList *head2){

    SinglyLinkedList *newHead = nullptr;

    while( head1 != nullptr && head2 != nullptr){
        // Storing the node with lower value at the end of linked list
        if( head1->value < head2->value){
            Node *temporary = head1;
            head1 = head1->next;
            temporary->next = newHead;
            // Shifting head to new head of the linked list
            newHead = temporary;
        }

        else{
            Node *temporary = head2;
            head2 = head2->next;
            temporary->next = newHead;
            // Shifting head to new head of the linked list
            newHead = temporary;
        }
    }

    // Adding remaining nodes in the linked lists

    while( head1 != nullptr ){
        Node *temporary = head1;
        head1 = head1->next;
        temporary->next = newHead;
        newHead = temporary;
    }

    while( head2 != nullptr ){
        Node *temporary = head2;
        head2 = head2->next;
        temporary->next = newHead;
        newHead = temporary;
    }

    return newHead;
}

Now practice some merge two sorted linked lists problems 

Frequently Asked Questions

How do you explain a linked list in an interview?

In an interview, a linked list can be explained as a data structure comprising nodes, where each node stores data and a reference to the next node. Linked lists are linear structures, ideal for dynamic data storage since they don't require contiguous memory allocation. 

What is head and tail in Linkedlist?

The "head" of a linked list is its first node, serving as the entry point for traversal. Conversely, the "tail" is the last node, and its reference to the next node points to null, signifying the list's end. Heads are used to begin operations, while tails are essential for the efficient appending of elements.

What are the three 3 types of linked list?

The three primary types of linked lists are singly linked lists, doubly linked lists, and circular linked lists. Singly linked lists enable traversal in one direction with nodes pointing to the next node. Doubly linked lists extend this by allowing traversal in both directions, with nodes pointing to both the next and previous nodes. Circular linked lists are a variation that forms a closed loop, with the tail node's reference pointing back to the head node.

What type of memory allocation is used when a linked list is being used?

Linked lists use dynamic memory allocation. Unlike arrays that allocate contiguous memory blocks, linked lists allocate memory for each node separately as needed. This dynamic allocation allows linked lists to efficiently adjust their size during runtime, making them flexible and suitable for scenarios where the data structure's size is uncertain or variable.

Conclusion

The article above discussed linked lists, their applications, and some linked list interview questions. We have also sorted the linked list of interview questions based on their difficulty, making them easier to read.

Also see, Manual testing interview questions

Some of the articles on linked lists that you might feel useful

• Identical Linked Lists
   
• Learn the basics of linked lists
   

Refer to our guided paths on Coding Ninjas Studio to solve Practice Interview Problems Of Top Tech Companies. Enrol in our courses and refer to the mock test and problems available.