C++ linked list interview questions

Table of contents

Circular linked list

This is a typical interview question. Given a singly linked list. Write a function that detects if the linked list is circular (has a loop) which means the last node points to another node in the list

Algorithm

Explanation: There are several ways to solve this problem. One solution is to simultaneously iterate through the list using two pointers with different speeds. For example, if the first pointer moves one node at a time and the second pointer moves two nodes at a time then they are expected to meet some time after they enter the loop. On the other hand, if the list does not contain any loop then the faster pointer will just hit the end of the loop.

Implementation

Here is an example circular linked list c program sample code

Linked list nth node from the end

Given a singly linked list. Write a function that returns the nth node from the end of the list.

Algorithm

Let (n) be the position (from the end of the list) of the node that we are trying to find
Count the number of nodes (c) by looping through the list
Find the difference d = c – n
Loop from the beginning of the list (d) times. You will find the desired node.

Note that if c is 1000 and n is 0 then you need to loop c + d = c + (c – n) = 2000 times. This is the worst case but if n is 1000 then you need to loop only 1000 times which is the best case. Another solution is to setup two pointers (n) nodes apart then keep looping until the second pointer hits the end of the list. In that case the first pointer will be pointing to the desired node. The second solution requires also two loops. The first loop is used to set the pointers apart by (n) nodes so it run (n) times. The second loop iterates until the second pointer hits the end of the list so it runs c – n times. In total we have n + (c – n) = c. Applying the same numbers we only loop 1000 times in the worst case. As you can see the second solution is a little bit better than the first solution however both have the same running time complexity because O(n) is practically the same as O(2n) when (n) is very large

Implementation

Here is the code to find nth node in linked list c++

Reverse linked list

Given a singly linked list. Write a function that reverses the linked list. Provide explanation and logic.

Algorithm

An iterative solution is to use two pointers. The first pointer points to the current node and the other pointer points to the next node. You loop through the list while redirecting each node’s pointer and make it point to the previous node. Please refer to the code below for more details.

Implementation

Here is an example reverse linked list c++ code

Reverse linked list recursively

Given a singly linked list. Write a function to reverse the linked list recursively

Algorithm

The linked list can be viewed as the concatenation of the first node and the rest of the nodes. Taking this into account we can recursively reverse the rest of the nodes then append the first node to the end of the list. The tricky part is how to append the first node to the end without visiting all nodes. The code below demonstrates that.

Implementation

Here is an example reverse linked list program code in C++

Thanks for reading. Please use the comments section below for feedback.

Add a Comment

Your email address will not be published. Required fields are marked *