C++ linked list interview questions
Table of contents
- Circular linked list
- Linked list nth node from the end
- Reverse linked list
- Reverse linked list recursively
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
//Includes #include <iostream> using namespace std; //Number of elements int num = 15; //Define Node struct Node { int data; Node* next; }; //Create a sample list of (num) nodes //The last node points to the second node Node* CreateListWithLoop() { Node* head = new Node; Node* curr = head; //Create nodes and fill each node with some integer (i) for (int i = 1; i <= num; i++) { curr->data = i; curr->next = new Node; //Make the last node point to the second node in the list if (i != num) { curr = curr->next; } else { curr->next = head->next; } } return head; } //Detect if the list contains a Loop bool ListContainsLoop(Node * head) { //Initialize both pointers Node* sp = head; Node* fp = head; //Loop in the list while(sp && fp) { //Advance the fast pointer fp = fp->next; //If the fast pointer is equal to the slow //pointer then there is a loop in the list if(fp == sp) return true; //If the fast pointer is null then we reached //the end of the list without detecting a loop if(fp == NULL) return false; //Advance the fast pointer one more time fp = fp->next; //Check again if(fp == sp) return true; //Slow pointer is advanced only once sp = sp->next; } //No loop return false; } //Main function void main() { //Create list with loop Node* head = CreateListWithLoop(); //Check if the list contains a loop if (ListContainsLoop(head)) { cout << "List contains a loop" << endl; } else { cout << "List does not contain a loop" << endl; } } |
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++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <iostream> using namespace std; //Number of elements int num = 15; //Define Node struct Node { int data; Node* next; }; //Create a sample list of (num) nodes Node* CreateList() { Node* head = new Node; Node* curr = head; //Create nodes and fill each node with some integer (i) for (int i = 1; i <= num; i++) { curr->data = i; curr->next = new Node; //The pointer in the last node must be NULL if (i != num) { curr = curr->next; } else { curr->next = NULL; } } return head; } //Get node position int Position(Node* head, int pos) { Node* p1 = head; Node* p2 = head; //Set the two pointers apart by (pos) positions for (int i = 1; i < pos; i++) p2 = p2->next; //Keep looping until p2 hits the end of the list while (p2->next != NULL) { p1 = p1->next; p2 = p2->next; } //P1 should be pointing to the desired node return p1->data; } void main() { //Create List Node* head = CreateList(); //Print all positions for (int i = 1; i <= num; i++) { cout << "Node " << i << " = " << Position(head, i) << endl; } } |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
//Includes #include <iostream> //Number of elements int num = 10; //Define Node struct Node { int data; Node* next; }; //Create a sample list of (num) nodes Node* CreateList() { Node* head = new Node; Node* curr = head; //Create nodes and fill each node with some integer (i) for (int i = 1; i <= num; i++) { curr->data = i; curr->next = new Node; //Last node pointer is NULL if (i != num) { curr = curr->next; } else { curr->next = NULL; } } return head; } //This function reverses the list Node* ReverseList(Node * head) { //We need two pointers p1 and p2 //p1 points to the current node //and p2 points to the next node Node* p1 = head; Node* p2 = head->next; //The first node will be the last node //after reverse so it should not be //pointing to any other node p1->next = NULL; //Loop in the list while(p2) { //Save p2->next because we need it later //after we make it point to the previous node Node* t = p2->next; //Make the node point to the previous node p2->next = p1; //Advance both pointers p1 and p2 //and recall we need to use the saved //value for p2 since we changed it //above p1 = p2; p2 = t; } //Once the loop is done p1 will carry the head //pointer return p1; } //Utility function to print the list void PrintList(Node * head) { while(head) { std::cout << head->data << std::endl; head = head->next; } std::cout << std::endl; } //Main function void main() { //Create a sample list Node* head = CreateList(); //Print list before reverse PrintList(head); //Reverse list head = ReverseList(head); //Print list after reverse PrintList(head); } |
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++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
//Includes #include <iostream> //Reverse linked list solution explanation //Number of elements int num = 10; //Define Node struct Node { int data; Node* next; }; //Create a sample list of (num) nodes Node* CreateList() { Node* head = new Node; Node* curr = head; //Create nodes and fill each node with some integer (i) for (int i = 1; i <= num; i++) { curr->data = i; curr->next = new Node; //Last node pointer is NULL if (i != num) { curr = curr->next; } else { curr->next = NULL; } } return head; } //This function recursively reverses the list Node* ReverseListRecursively(Node* head) { //If the list is empty return null if (head == NULL) return NULL; //If the list is composed from one node only //then return head if (head->next == NULL) return head; //Reverse the rest of the nodes Node* r = ReverseListRecursively(head->next); //Append the first node to the end of the list head->next->next = head; //The last node must not point to any other node head->next = NULL; //Pointer r is the new head return r; } //Utility function to print the list void PrintList(Node * head) { while(head) { std::cout << head->data << std::endl; head = head->next; } std::cout << std::endl; } //Main function void main() { //Create a sample linked list Node* head = CreateList(); //Print list before reverse PrintList(head); //Reverse list head = ReverseListRecursively(head); //Print list after reverse PrintList(head); } |
Thanks for reading. Please use the comments section below for feedback.