I'm getting segmentation fault(SIGSEGV) in my code

Question

Given a singly linked list of size N of integers. The task is to check if the given linked list is palindrome or not.

Input: First line of input contains number of testcases T. For each testcase, first line of input contains length of linked list N and next line contains N integers as data of linked list.

Output: For each test case output will be 1 if the linked list is a palindrome else 0.

User Task: The task is to complete the function isPalindrome() which takes head as reference as the only parameter and returns true or false if linked list is palindrome or not respectively.

Constraints:
1 <= T <= 103
1 <= N <= 50

Example(To be used only for expected output):

Input:
2
3
1 2 1
4
1 2 3 4

Output:
1
0

Explanation: Testcase 1: 1 2 1, linked list is palindrome.

My Code:


 #include <stdio.h>
 #include <stdlib.h>
 #include <iostream>
#include <stack>
using namespace std;
/* Link list Node */
struct Node {
  int data;
  struct Node *next;
  Node(int x) {
    data = x;
    next = NULL;
  }
};
void append(struct Node** head_ref, struct Node **tail_ref, int new_data)
{
    struct Node* new_node = new Node(new_data);

    if (*head_ref == NULL)
       *head_ref = new_node;
    else
       (*tail_ref)->next = new_node;
    *tail_ref = new_node;
}
bool isPalindrome(Node *head);
/* Driver program to test above function*/
int main()
{
  int T,i,n,l;
    cin>>T;
    while(T--){
    struct Node *head = NULL,  *tail = NULL;
        cin>>n;
        for(i=1;i<=n;i++)
        {
            cin>>l;
            append(&head, &tail, l);
        }
    cout<<isPalindrome(head)<<endl;
    }
    return 0;
}

}
/*This is a function problem.You only need to complete the function given below*/

/*
struct Node {
  int data;
  struct Node *next;
  Node(int x) {
    data = x;
    next = NULL;
  }
};
*/
/*You are required to complete this method */
bool isPalindrome(Node *head)
{
    Node *front=head;

    if(head==NULL)
    {
        return -1;
    }
    int len=0;
    while(front!=NULL)
    {
        front=front->next;
        len++;
    }
    front=head;
    stack <int> s;
    if(!(len%2))
    {
        int m=(len/2);
        while(m-- && front)
        {
            s.push(front->data);
            front=front->next;
        }
        int k=(len/2);
        while(k-- && !s.empty())
        {
            int q= s.top();
            s.pop();
            if(q==front->data)
            {
                front=front->next;
                continue;
            }
            else
            {
                break;
            }
        }
    }
    else
    {
        int m=(len/2)-1;
        while(m-- && front)
        {
            s.push(front->data);
            front=front->next;
        }
        front=front->next;
        int k=(len/2)-1;
        while(k-- && !s.empty())
        {
            int q= s.top();
            s.pop();
            if(q==front->data)
            {
                front=front->next;
                continue;
            }
            else
            {
                break;
            }
        }
    }
    if(s.empty())
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

I'm getting Segmentation Fault-SIGSEGV.

Why are you hand-rolling a linked list rather than just using `std::list` or `std::forward_list`? — Jesper Juhl, Jul 06 '19 at 15:57
@JesperJuhl look at the comments in the code, the definition of Node is not free but is an input — bruno, Jul 06 '19 at 16:00
@JesperJuhl It's an educational task. You surely know this. It's only about the billionth time we've seen it here! — Lightness Races in Orbit, Jul 06 '19 at 16:01
@LightnessRacesinOrbit Debug in the sense? Correcting the code after executing it? Though I've done it. — The Puzzler, Jul 06 '19 at 16:03
When your program crashes, you are supposed to engage in the act of _debugging_ to find out what went wrong. Usually you'll recruit the assistance of a tool known as a _debugger_ to aid in this task. If you haven't done that yet, you're not ready to ask Stack Overflow for volunteer help. — Lightness Races in Orbit, Jul 06 '19 at 16:03
@LightnessRacesinOrbit Ok. I get you. I've debugged my code. But when I submit it, I get SIGSEGV error. — The Puzzler, Jul 06 '19 at 16:05
For example, a debugger will tell you exactly which line crashes and what values variables have at that point. — melpomene, Jul 06 '19 at 16:05
Something doesn't add up. Had you debugged the problem, you'd surely know more than "I get SIGSEGV error". You'd know which part of the program caused a memory fault, in what manner, and [to some degree] why. We cannot (and would not) do that part of the work remotely for you. — Lightness Races in Orbit, Jul 06 '19 at 16:07
I recommend using local development tools, not online stuff. — melpomene, Jul 06 '19 at 16:09
@ThePuzzler - A debugger won't magically tell you what the bug is. But it will stop your program when the segfault happens and let you inspect variable values, along with a stack trace of what led you to that situation. It also lets you set breakpoints and run the code line-by-line and inspect variables at every step. All these things should help in getting a handle on what you are doing wrong. And debuggers can do *much more* than that. — Jesper Juhl, Jul 06 '19 at 16:10
@ThePuzzler I know this is supposed to be an exercise in creating your own linked list, but why in the same code are you using `#include `? You're allowed to use the C++ stack class `std::stack`, but not allowed to use `std::list`? It's gotten to the point now where even the teachers are getting themselves tied up in knots trying to figure out what STL components to use and what not to use. If this is not a school exercise, then you've written a half-baked program that uses STL here, no STL there, etc., and few if any programmers would write a program like that. — PaulMcKenzie, Jul 06 '19 at 16:59
When debugging your code of a linked list, use pen and paper to draw the nodes and how they are connected. — Thomas Matthews, Jul 06 '19 at 17:03
Usually a debugger application running on your local computer is faster and easier to use than an online debugger (also, internet connections can hiccup, drop-out or disappear). — Thomas Matthews, Jul 06 '19 at 17:04
Please see https://ericlippert.com/2014/03/05/how-to-debug-small-programs/. Debugging your own code is an essential skill in programming that you need to be able to do yourself. — eesiraed, Jul 06 '19 at 17:44

score 1 · Answer 1 · answered Jul 06 '19 at 16:09

1

Consider, what's going on with this code with len = 1:

int m=(len/2)-1;
while(m-- && front)
{
    s.push(front->data);
    front=front->next;
}

m is equal (0 / 2) - 1, which is -1. Which means while(m-- && front) will exhaust whole list. As a result s is now of size 1 and front points to NULL. Now you try:

front=front->next;

which causes segfault, as front is NULL.

Try changing m-- conditions to m-- > 0.

answered Jul 06 '19 at 16:09

Radosław Cybulski

2,952
10
21

Which is easily discoverable with a debugger. Which OP should use. – Jesper Juhl Jul 06 '19 at 16:14
Thanks a lot. But that gives a wrong output. – The Puzzler Jul 06 '19 at 16:15
Then maybe you have another bug that has now surfaced. Time for that debugger again.... – Martin James Jul 06 '19 at 18:18
You probably have off by one error somewhere. Possibly `m-- >= 0`? – Radosław Cybulski Jul 06 '19 at 18:29
Thanks everyone. I was able to submit my code successfully! – The Puzzler Jul 06 '19 at 21:17
One more thing... If the arguement of while loop is negative, does it still run? – The Puzzler Jul 06 '19 at 21:44
Yes. `while(m)` will run as long as `m` is true. And number of any type is considered true in C++, when it's not equal to zero. Negative numbers are true just as positive. – Radosław Cybulski Jul 07 '19 at 06:08

I'm getting segmentation fault(SIGSEGV) in my code

1 Answers1