1. What is a Linked List?
A linked list is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence.
2. Explain the types of Linked Lists.
Types of Linked Lists include singly linked lists, doubly linked lists, and circular linked lists.
3. How will you find the middle element of a singly linked list without iterating the list more than once?
To solve this problem, we can use the two-pointer method. You have two pointers, one fast and one slow, in the two-pointer approach. The fast pointer travels two nodes per step, while the slow pointer only moves one. The slow pointer will point to the middle node of the linked list when the fast pointer points to the last node, i.e. when the next node is null.
Node* getMiddle(Node *head){ struct Node *slow = head; struct Node *fast = head; if (head) { while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; } } return slow;}Time Complexity: O(n)
Space Complexity: O(1)
4. How will you remove a cycle from a linked list?
One method of identifying the cycle is Floyd's cycle detect technique, popularly known as the tortoise and hare algorithm since it uses two pointers/references that move at opposite speeds. If there is a cycle, after a limited number of steps, the two pointers (say, slow and fast) will point to the same element.
It's interesting to note that the element where they meet will be the same distance from the loop's start (continuing to traverse the list in the same, forward direction) as the loop's start is from the list's head. That is, if the linear component of the list contains k elements, the two pointers will meet inside a loop of length m at a location m-k from the loop's start or k elements from the loop's 'end' (of course, it's a loop, so there is no 'end' - it's just the ‘start' again). That gives us a technique to find the loop's beginning.
Once a cycle has been detected, keep fast pointing to the element where the loop for the previous step ended, but reset slow to point back to the beginning of the list. Now, one element at a time, move each pointer. Fast will keep looping because it started inside the loop. Slow and fast will meet again after k steps (equivalent to the distance between the start of the loop and the head of the list). This will serve as a pointer to the beginning of the loop.
It's now simple to set slow (or fast) to point to the loop's starting element and traverse the loop until slow returns to the starting element. Slow is referring to the 'last' element list at this point, and its next pointer can be adjusted to null.
Implementation:
Node* getLastNode(Node* head) { Node* slow = head; Node* fast = head; // find the intersection point using Tortoise and Hare algorithm while (fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; } //check if there is no loop if (fast->next == NULL) { return NULL; } slow = head; // run this loop till both the references are one short of the start of the loop while (slow->next != fast->next) { slow = slow->next; fast = fast->next; } // Now the fast pointer is pointing to the start of the loop return fast;}Node* getLastNode = findStartOfLoop(head);getLastNode->next = null;Time Complexity: O(n)
Space Complexity: O(1)
5. What algorithm will you implement to find similar elements from two Linked Lists given and return the result in the form of a Linked List? Assume there are no duplicates.
Create an empty hash table and set the result list to NULL. While traversing List1, insert the element in the hash table for each element visited in List1. While traversing List2, look for the entries in the hash table for each element visited in List2. If the element is already existing, add it to the result list. If the element isn't present, it is to be ignored.
The overall time and space complexity are linear.
Node* getIntersection(Node* head1, Node* head2){ unordered_map < int > m; Node* n1 = head1; Node* n2 = head2; Node* head = NULL; // loop stores all the elements of list1 in hset while (n1) { m[n1->value] = 1; n1 = n1->next; } // For every element of list2 present in hset // loop inserts the element into the result while (n2 != null) { if (m[n2->value] == 1) { Node* temp = new Node(); temp->value = n2->value; temp->next = head; head = temp; } n2 = n2->next; } return head;}6. Why is merge sort a better option than quicksort for linked lists?
- When it comes to linked lists, there are a few things to keep in mind. The issue is unique due to the memory allocation differences between arrays and linked lists. Unlike arrays, linked list nodes in memory may not be adjacent.
- We can insert items in the middle of a linked list in O(1) extra space and O(1) time if we are given a reference/pointer to the previous node, unlike an array. As a result, the merge sort operation can be accomplished without the need for additional linked list space.
- We can do random access in arrays since the elements are continuous in memory. In contrast to arrays, we can't access a linked list at random.
- Quick Sort necessitates a great deal of this type of access. Because we don't have a continuous block of memory, we have to travel from the head to the i'th node to get to the i'th index in a linked list. Merge sort accesses data in a sequential manner, with less requirement for random access.
7. The task is to determine pairs in a doubly-linked list whose sum equals the provided value ‘val’ without consuming any extra space for a given sorted doubly-linked list of positive distinct entries. The expected complexities are O(n) time and O(1) space.
The approach is as follows:
- Two pointer variables are to be initialized to find the possible elements in the sorted doubly linked list. Initialize num1 with the head of the doubly linked list,i.e., num1=head, and num2 with the last node of the doubly linked list, i.e., num2=lastNode.
- If the current sum of num1 and num2 is less than Val, then we advance num1 in the forward direction. If the current total of the num1 and num2 is greater than x, then num2 is moved in the backward direction.
- When the two pointers cross each other (num2->next = num1) or they become equal (num1 == num2), the loop ends. The condition "num1==num2" will handle the circumstance where no such pairs are present.
Implementation:
vector<pair<int,int>> sumPair(struct Node *head, int val){ // Two pointers are to be set, one to the beginning // and the other to the last of the DLL. struct Node *num1 = head; struct Node *num2 = head; while (num2->next != NULL) //to get to the last node num2 = num2->next; vector<pair<int,int>> ans; // The loop ends when two pointers // cross each other or they are equal while (num1 != num2 && num2->next != num1) { if ((num1->value + num2->value) == val) { ans.push_back(make_pair(num1->value,num2->value)); // move num1 in the forward direction num1 = num1->next; // move num2 in the backward direction num2 = num2->prev; } else { if ((num1->value + num2->value) > val) num2 = num2->prev; else num1 = num1->next; } } return ans;}Time Complexity: O(n)
Space Complexity: O(1)
8. How will you modify a linked list of integers so that all even numbers appear before all odd numbers in the modified linked list? Also, keep the even and odd numbers in the same order.
Example:
Input: 17->15->8->12->10->5->4->1->7->6->NULL
Output:
8->12->10->4->6->17->15->5->1->7->NULL
Algorithm:
The approach is to divide the linked list into two sections, one with all even nodes
and the other with all odd nodes. In order to split the Linked List, traverse the original Linked List and move all
odd nodes to a new Linked List. The original list will include all the even nodes at the end of the loop, while the
odd node list will have all the odd nodes. We must place all the odd nodes at the end of the odd node list to maintain
the same ordering of all nodes. And, in order to do it in real-time, we'll need to maintain track of the last pointer
in the odd node list. Finally, the odd node linked list is to be attached after the even node linked list.
Implementation:
Node* separateEvenOdd(struct Node *head){ // Starting node of the list having // even values Node *evenStart = NULL; // Starting node of the list having odd values Node *oddStart = NULL; // Ending node of the list having even values Node *evenEnd = NULL; // Ending node of the list having odd values Node *oddEnd = NULL; // Node for list traversal. Node *currentNode; for(currentNode = head; currentNode != NULL; currentNode = currentNode -> next) { int value = currentNode -> value; // If the current value is even, add // it to the list of even values. if(value % 2 != 0) { if(oddStart != NULL) { oddEnd -> next = currentNode; oddEnd = oddEnd -> next; } else { oddStart = currentNode; oddEnd = oddStart; } } // If current value is odd, add // it to the list of odd values. else { if(evenStart != NULL) { evenEnd -> next = currentNode; evenEnd = evenEnd -> next; } else { evenStart = currentNode; evenEnd = evenStart; } } } // If any of the two- odd list or even list is empty, // no change is required if(!oddStart || !evenStart) { return; } // Add the odd list after the even list. evenEnd -> next = oddStart; oddEnd -> next = NULL; // Modify the head pointer to // the start of the even list. head = evenStart; return head;}Time Complexity: O(n)
Space Complexity: O(1)
9. Given a linked list and a number n, you have to find the sum of the last n nodes of the linked list in a single traversal. Explain your approach in brief.
The use of two-pointers will require a single traversal. We will have to maintain two pointers – reference pointer and main pointer. Both these pointers will be initialized to head. First, the reference pointer will be moved to n nodes from the head, and while traversing, we will keep adding the values and store them into a variable called sum1. Now both the pointers will move simultaneously until the reference pointer reaches the end of the list and while traversing, we will keep adding the values of the nodes. The reference pointer is storing this sum in the variable sum1, and the main pointer will be storing it in sum2. Now, (sum1 – sum2) is the answer, that is the required sum of the last n nodes.
int getSum(Node* head, int n){ if (n <= 0) return 0; int sum1 = 0, sum2 = 0; struct Node* ptr1 = head; struct Node* ptr2 = head; // the sum of the first n nodes is to be calculated for (ptr1 = head; ptr1 != NULL; ptr1 = ptr1->next;) { sum += ptr1->value; n--; if(n == 0) break; } // now there is a distance of n nodes between the two pointers // move to the end of the linked list while (ptr1 != NULL) { // sum of all the nodes sum1 += ptr1->value; // sum of the first length - n nodes sum2 += ptr2->value; ptr1 = ptr2->next; ptr2 = ptr2->next; } // returning the required sum return (sum1 - sum2);}Time Complexity is O(n) and space complexity is O(1).
10. How will you find the length of a linked list which contains a cycle?
The algorithm to determine the length of the list:
- At a time, pointer A advances one node while pointer B advances two nodes.
- Starting from the head, they move until B reaches null (no loop) or A and B refer to the same node.
- Now, if A simply advances, A will run into B again. The length of the loop, let's call it x, may be calculated from this.
- Begin again from the head, but this time have a pointer C which has moved x nodes, followed by a pointer D behind it. Both will move one node further at a time.
- When they meet, the length of the linked list with a loop is equal to the number of nodes traversed by D plus x.
int calcLen( Node* head ){ struct Node *A = head, *B = head; while ( A && B && B->next ) { A = A->next; B = B->next->next; /* If slow_p and fast_p meet at some point then there is a loop */ if (A == B) { int x = 1; struct Node *t = A; while (t->next != A) { x++; t = t->next; } } } struct Node *C = head, *D = head; int y = 0; for ( int i = 0; i < x; i++ ) { C = C->next; } while( C != D ) { y++; C = C->next; D = D->next; } return x+y;} Time Complexity: O(n)
Space Complexity: O(1)
11. Given a value x and a sorted doubly linked list of different nodes (no two nodes have the same data). Count the number of triplets in the list that add up to x. The expected time complexity is O(n^2) and the expected space complexity is O(1).
Following the approach os using two pointers:
From left to right, traverse the doubly linked list. Initialize two pointers for each current node during the traversal: first = pointer to the node next to the current node, and last = pointer to the list's last node. Count the number of pairs in the list that add up to the value (x – the current node's data) from the first to the last pointer (algorithm described in Q8). This number should be added to the total count of triplets. Pointer to the last node can be retrieved only once at the beginning.
Implementation:
int pairCount(struct Node* num1, struct Node* num2, int val){ int cnt = 0; // The loop terminates when either of two the pointers // become NULL, or they cross each other or they become equal while (num1 != NULL && num2 != NULL && num1 != num2 && num2->next != num1) { // pair found if ((num1->value + num2->value) == val) { cnt++; // second is moved in backward direction num2 = num2->prev; // first is moved in forward direction num1 = num1->next; } // else first is moved in forward direction else if ((num1->value + num2->value) < val) num1 = num1->next; // if sum is greater than 'value' // second is moved in backward direction else num2 = num2->prev; } // required number of pairs return cnt;}// function to count triplets in a sorted DLL// whose sum equals a given value 'x'int tripletCount(struct Node* head, int x){ // check if the list is empty if (!head) return 0; int cnt = 0; struct Node* current = head; struct Node* last = head; struct Node* first; // get pointer to the last node of the doubly linked list while (last->next) last = last->next; // traverse the doubly linked list while (current) { // for every current node first = current->next; // count the number of pairs with sum(x - current->data) in the range // first to last and add it to the 'cnt' of triplets cnt += pairCount(first, last, x - current->value); current = current->next; } // required number of triplets return cnt;}12. Given a linked list, find the length of the longest palindrome list that appears in that linked list using O(1) extra space.
The concept is built on reversing a linked list iteratively. We loop through the given linked list, reversing each prefix of the linked list one by one from the left. We discover the longest common list beginning with the reversed prefix and the list after the reversed prefix, after reversing a prefix.
Time complexity is O(n^2).
Implementation:
int calcCommon(Node *x, Node *y){ int cnt = 0; // count common in the list starting // from node x and y while (1) { // increase the count by one for same values if (x->value == y->value) cnt++; else break; x = x->next; y = y->next; } return cnt;}// Returns length of the longest palindrome sublistint maxPalindrome(Node *head){ Node *previous = NULL, *current = head; int answer = 0; // loop running till the end of the linked list while (1) { if(current==NULL) break; // reversed sublist from head to current Node *next = current->next; current->next = previous; // check for odd length palindrome answer = max(result, 2*calcCommon(previous, next)+1); // check for even length palindrome answer = max(result, 2*calcCommon(current, next)); // update previous and current for next iteration previous = current; current = next; } return answer;}13. In a standard Doubly Linked List, two address fields are required to contain the addresses of previous and next nodes. Can you create a doubly linked list using only one space for the address field with every node?
Yes, there is a memory-saving version of the Doubly Linked List that uses only one space for the address field in each node. Because the list uses the bitwise XOR operation to save space for one address, it is known as the XOR Linked List or Memory Efficient. Instead of storing actual memory addresses, each node in the XOR linked list stores the XOR of previous and next node addresses.
In the XOR representation, let's call the address variable npx (XOR of next and previous).
We can traverse the XOR Linked List in both forward and reverse directions while traversing it. We must remember the address of the previously visited node when traversing the list in order to determine the address of the next node.
Node W:
npx = 0 XOR add(X)
Node X:
npx = add(W) XOR add(Y)
Node Y:
npx = add(X) XOR add(Z)
Node Z:
npx = add(Y) XOR 0
Calculation:
npx(Y) XOR add(X)
=> (add(X) XOR add(Z)) XOR add(X) //
npx(Y) = add(X) XOR add(Z)
=> add(X) XOR add(Z) XOR add(X)
// w^x = w^x and (w^x)^y = w^(x^y)
=> add(Z) XOR 0
// x^x = 0
=>
add(Z)
// x^0 = x
14. Code Snippet: Node Structure
// Node structure for a singly linked list
struct Node {
int data;
struct Node* next;
};