Copy doubly linked list C++
IntroductionOne of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit. Show Problem StatementIn this problem, we are given a linked list of length N having two pointers in each node. The first pointer points to the next node of the list, and the second one is a random pointer which can point to any node of the linked list, or NULL. Now we are asked to write a program that clones the given list in O(1) space. Note: The cloned linked list should consist of exactly N new nodes, where the value of each node is the same as the corresponding value in original linked list and the next and random pointers of the new nodes should point to new nodes in the cloned linked list in such a way that the pointers in the original linked list and cloned linked state represent the same list state. Finally, you have to return the head of the cloned linked list. Problem statement understandingFirst, we need to understand what cloning a linked list means.
From the above figure, we can see that the addresses of the cloned nodes are different, but the structure and data of the linked list are the same.
ExampleInput linked list Output: A new linked list that is a copy of the original list Now I think from the above examples, the problem statement is clear. So let's see how we will approach it. Any Ideas?
Lets move to the next section. ApproachOur approach will be simple:
Let's move to the algorithm section to see the above approach step by step in detail. Algorithm
Dry RunCode Implementation
#include
using namespace std;
/* Structure of a node */
struct Node
{
int data;
Node *next,*random;
Node(int a)
{
data = a;
next = NULL;
random = NULL;
}
};
/* This function is used to print the linked list */
void printingLinkedList(Node *head)
{
Node *ptr = head;
while (ptr != NULL)
{
cout << "Data = " << ptr->data << ", Random = " << ptr->random->data << endl;
ptr = ptr->next;
}
}
/* This function will return the cloned linked list */
Node* cloningLinkedList(Node *head)
{
Node* curr = head, *temp;
while (curr != NULL)
{
temp = curr->next;
curr->next = new Node(curr->data);
curr->next->next = temp;
curr = temp;
}
curr = head;
while (curr != NULL)
{
if(curr->next)
curr->next->random = curr->random ?
curr->random->next : curr->random;
curr = curr->next?curr->next->next:curr->next;
}
Node* original = head, *copy = head->next;
temp = copy;
while ((original !=NULL) && (copy != NULL))
{
original->next = original->next? original->next->next : original->next;
copy->next = copy->next?copy->next->next:copy->next;
original = original->next;
copy = copy->next;
}
return temp;
}
int main()
{
Node* head = new Node(1);
head->next = new Node(3);
head->next->next = new Node(5);
head->next->next->next = new Node(7);
head->random = head->next->next;
head->next->random = head->next->next->next;
head->next->next->random = head->next;
head->next->next->next->random = head;
cout << "Original linked list : \n";
printingLinkedList(head);
cout << "\nCloned linked list : \n";
Node *clone = cloningLinkedList(head);
printingLinkedList(clone);
return 0;
}
OutputOriginal linked list : Cloned linked list : Time Complexity: O(N), since we are only traversing over the length of the linked list. Let us check your understanding!!Think before you answer What is the Space complexity for this algorithm? O(n) O(1) O(logn) None of these So, in this article, we have tried to explain the most efficient approach to rearrange a given linked list in place. This is an important problem when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes visit Linked List. |