My accepted C++ solution is giving Segentation fault in my Ubuntu


  • 0
    S

    In the following code,

    #include <cstdio>
    #include <cstdlib>
    using namespace std;
    
    //Definition for singly-linked list.
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    
    class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            // finding head
            ListNode *current = head, *previous = NULL, *start = head, *temp, *distinct;
            // if(current->next != NULL && current->val == current->next->val) {
                
            // }
            if(current == NULL) return NULL;
            while((previous!=NULL && previous->val == current->val) || (current->next!=NULL && current->next->val == current->val)) {
                previous = current;
                current = current->next;
                if(current == NULL) return NULL;
            }
            head = current;
            
            // delting all nodes from [start, head)
            current = start;
            while(current != head) {
                temp = current;
                current = current->next;
                free(temp);
            }
            
            /* deleting the nodes which have duplicates */
            distinct = head;
            while(distinct->next != NULL && distinct->next->next != NULL) {
                if(distinct->next->val == distinct->next->next->val) {
                    while(distinct->next != NULL && distinct->next->next != NULL && distinct->next->val == distinct->next->next->val) {
                        temp = distinct->next;
                        distinct->next = distinct->next->next;
                        free(temp);        // LINE 68  <<<------------------------------------------------
                    }
                    temp = distinct->next;
                    distinct->next = distinct->next->next;
                    free(temp);
                }
                else distinct = distinct->next;
            }
            
            return head;
            
        }
    };
    
    void printlist(ListNode* head) {
        while(head != NULL) {
            printf("%d ",head->val );
            head = head->next;    
        }
        
    }
    
    int main(int argc, char const *argv[])
    {
        ListNode n1 = ListNode(1);
        ListNode n2 = ListNode(2);
        ListNode n3 = ListNode(2);
    
        ListNode *head = &n1;
        head->next = &n2;
        head->next->next = &n3;
    
        Solution obj;
        head = obj.deleteDuplicates(head);
        printlist(head);
        return 0;
    }
    

    At line 68 : free(temp) , My program is throwing a segmentation fault , although the statement looks completely fine to me. Please help.

    On using gdb , I get this following error

    Program received signal SIGSEGV, Segmentation fault.
    _int_free (av=0x7ffff7acf760 <main_arena>, p=0x7fffffffdcb0, have_lock=0) at malloc.c:3960
    3960 malloc.c: No such file or directory.
    (gdb) where
    #0 _int_free (av=0x7ffff7acf760 <main_arena>, p=0x7fffffffdcb0, have_lock=0) at malloc.c:3960
    #1 0x00000000004009cb in Solution::deleteDuplicates (this=0x7fffffffdca7, head=0x7fffffffdcb0) at leetcode.cpp:68
    #2 0x0000000000400810 in main (argc=1, argv=0x7fffffffddc8) at leetcode.cpp:101


  • 1
    N

    Your nodes are allocated in the STACK. You're trying to free the memory they're taking using free, which should be used for freeing memeory allocated in HEAP.


  • 0
    S

    What is wrong in that ?
    I am trying to free a 'temp' node which I no loned need...
    Can you explain what the mistake is exactly ?


  • 0
    N

    you can only use "free" to release memory allocated with "malloc".These are C way to dynamically create/delete memory. For C++, you should use new/delete. Your temp is not really "temp", it is just one of n1, n2 or n3, they are allocated in the stack, not in the heap. basically, you create your linked list in a wrong way. normally, we create a linked list like this:

    ListNode *head = 0;
    head = new ListNode(1);
    head->next = new ListNode(10);
    head->next->next = new ListNode(5);

    etc.


  • 0
    S

    Thank you very much :) your comment was of great help...
    but a small correction... I think when you do this ListNode n1 = ListNode(1);
    node n1 is allocated on the stack of main function and not the heap. Am I wrong ?


  • 0
    N

    Sorry, I corrected my comment. ListNode n1(1); n1 is allocated on the stack, not the heap (which is also called free store). You're right. You cannot use delete/free to get the stack allocated memory back.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.