C++ Segmentation Fault when traversing linked list

Question

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;
}

What is the functionality of `mth_to_last()`? What does it do, semantically? — Azeem, Apr 05 '20 at 03:40
Returns the nth to last node in the linked list. So if the list was 1->2->3->4, and n is 2, it would return 3. — swing1234, Apr 05 '20 at 03:51

Azeem · Answer 1 · 2020-04-05T04:26:30.943

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:

Why is "using namespace std;" considered bad practice?

C++ Segmentation Fault when traversing linked list

1 Answers1