I tried to implement the following question: Clone a linked list with next and random pointer in O(1) space from geeks for geeks. But unfortunately, I am getting segmentation faults in my code. The logic used is in 4 steps:
- create a simple clone of the given list
- make the next pointer of each given list node point to its corresponding cloned node.
- Make each cloned node's arb pointer point to its corresponding original node.
- Then use this line to update the cloned node arb pointer: cloneNode->arb = cloneNode->arb->arb->next;
- return the head of the cloned list
The code is as follows:
class Solution
{
private:
void insertAtTail(Node* &head, Node* &tail, int d)
{
Node* newNode = new Node(d);
if(head == NULL)
{
head = newNode;
tail = newNode;
return;
}
tail->next = newNode;
tail = newNode;
}
public:
Node *copyList(Node *head)
{
//Write your code here
if(head == NULL )
return head;
Node* cloneHead = NULL;
Node* cloneTail = NULL;
//step 1: clone the original linked list
Node* originalNode = head;
while(originalNode != NULL)
{
insertAtTail(cloneHead,cloneTail,originalNode->data);
originalNode = originalNode->next;
}
//step 2: make the next pointer of the original node point to the clone nodes
originalNode = head;
Node* originalPrev = NULL;
Node* cloneNode = cloneHead;
while(cloneNode != NULL && originalNode != NULL)
{
originalPrev = originalNode;
originalNode = originalNode->next;
originalPrev->next = cloneNode;
cloneNode->arb = originalPrev;
cloneNode = cloneNode->next;
}
//step 3: clone the random pointers of the original node
cloneNode = cloneHead;
while(cloneNode != NULL)
{
cloneNode->arb = cloneNode->arb->arb->next;
cloneNode = cloneNode->next;
}
return cloneHead;
}
};
Output is coming as a Segmentation fault. The logic is explained in this video.
The code was written in this link.
Code is written in C++.
Any help in finding the mistake in my code will be much appreciated.