CODEWITHSUNDEEP
c++linked-listsegmentation-fault
swing1234
swing1234

Reputation: 233

C++ Segmentation Fault when traversing linked list

I am writing a program to find the nth to the last node in a linked list. The program produces the correct output, however, when I run the program I get a segmentation fault at the line while(fast). When I debugged the program using print statements, I noticed while(fast) gets executed even when fast pointer is NULL (i.e. fast goes beyond the end of the list).

Any suggestions on how to fix the segmentation error?

Here's my code:

#include <vector>
#include <iostream>
using namespace std;

struct Node {
public:
    int data;
    struct Node* next;
};

void insert(Node*& headPtr, int val) {
    Node* temp = new Node;
    temp->data = val;
    temp->next = headPtr;
    headPtr = temp;
}

Node* mth_to_last(Node* head, int m) {
    Node* fast = head;
    Node* slow = head;

    for(int i = 0; i < m; i++) {
        fast = fast->next;
    }

    while(fast) {
        fast = fast->next;
        slow = slow->next;
    }

    return slow;   
}

int main() {  
    Node* head;

    for(int i = 10; i >= 1; i--) {
        insert(head, i);
    }

    Node* res = mth_to_last(head, 4);
    cout << res->data << endl;
}

Upvotes: 0

Views: 191

Answers (1)

Azeem
Azeem

Reputation: 14667

It is Undefined Behavior.

You didn't initialize the head node before use (live):

Node* head = nullptr;

So, the while loop doesn't end because head contains some garbage value on start.

Also, you're not initializing next pointer of the first node either (head). Right now, it doesn't cause a problem because it's not being used. But, if you do start to use that, it'll cause problems i.e. more UB. So, you need to initialize that in the constructor e.g.:

struct Node {
    Node() : data{0}, next{nullptr} {}

    int data;
    Node* next;
};

Or, you can use default member initialization like this:

struct Node {
    int   data {0};
    Node* next {nullptr};
};

Note that the default visibility of a struct is public so you don't need to mention that unless there are private, public and protected access specifiers in the same struct.

Also, in C++, you can do:

Node* next;

instead of

struct Node* next;

Here's an example with the above changes: https://godbolt.org/z/uVD76J

Relevant thread:

Upvotes: 2

Related Questions