-2

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:

  1. create a simple clone of the given list
  2. make the next pointer of each given list node point to its corresponding cloned node.
  3. Make each cloned node's arb pointer point to its corresponding original node.
  4. Then use this line to update the cloned node arb pointer: cloneNode->arb = cloneNode->arb->arb->next;
  5. 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.

Evg
  • 23,109
  • 5
  • 38
  • 74
  • Did you try to run it in debugger? C++ can't be learned without learning to use debugger. – Öö Tiib May 27 '22 at 05:56
  • Actually, I am using online Coding platforms to code, hence debugging is not an option present there. Even if I used n IDE I won't be able to understand the test cases given in that platform. – subham basu roy chowdhury May 27 '22 at 06:08
  • 2
    "debugging is not an option" - absolutely false; Just think about possible test cases for your scenario, write them ([google test docs](https://google.github.io/googletest/) in case you don't know what to use), implement your code on your PC, and then debug all possible issues. When it's working (with your test cases), submit it to the platform. Writing a bunch of code, submitting it and failing, then asking in SO "guys my code does not work" doesn't make much sense. – pptaszni May 27 '22 at 06:47
  • Please don't add irrelevant tags. DSA tag stands for "digital signature algorithm". – Evg May 27 '22 at 08:17
  • @subhambasuroychowdhury *hence debugging is not an option present there* -- So the built-in excuse for not debugging the code is that you are using an online compiler? That is your issue, not ours -- you are expected to debug the code that you write. Install a compiler on your local PC and debug the code there. [Please read this thread](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). And after reading that thread, please see [why not debugging your code is worthy of a downvote](https://idownvotedbecau.se/nodebugging/). – PaulMcKenzie May 27 '22 at 08:30
  • 1
    *if you don't have time then don't comment* -- No, it doesn't work that way. First, the comment section *is* for comments, not answers. Second, telling the community to "shut up" because they are trying to get you to do the up-front work is not the way to go about things. – PaulMcKenzie May 27 '22 at 13:27
  • 1
    Second, the debugger has no idea what your program is supposed to do -- only you do. The debugger is there to see when given data, where your program goes against the plan you had on paper. Once you see the program go differently then the plan, then it's your job to, at the very least, identify where the problem is. We are not expecting you to fix the problem, but one thing you just simply shouldn't do is to dump code and not have any idea where your program is going wrong. – PaulMcKenzie May 27 '22 at 13:28

0 Answers0