Why is Hackerrank showing segmentation error for the following C code?

Question

Hackerrank Problem Description:

You are given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer. Insert this node at the tail of the linked list and return the head node of the linked list formed after inserting this new node. The given head pointer may be null, meaning that the initial list is empty.

Input Format

You have to complete the SinglyLinkedListNode insertAtTail(SinglyLinkedListNode head, int data) method. It takes two arguments: the head of the linked list and the integer to insert at tail. You should not read any input from the stdin/console.

The input is handled by code editor and is as follows: The first line contains an integer , denoting the elements of the linked list. The next lines contain an integer each, denoting the element that needs to be inserted at tail.

Constraints

Output Format

Insert the new node at the tail and just return the head of the updated linked list. Do not print anything to stdout/console.

The output is handled by code in the editor and is as follows: Print the elements of the linked list from head to tail, each in a new line.

Sample Input

5 141 302 164 530 474

Sample Output

141 302 164 530 474

Explanation

First, the linked list is NULL.

After inserting 141, the list is 141 -> NULL.

After inserting 302, the list is 141 -> 302 -> NULL.

After inserting 164, the list is 141 -> 302 -> 164 -> NULL.

After inserting 530, the list is 141 -> 302 -> 164 -> 530 -> NULL.

After inserting 474, the list is 141 -> 302 -> 164 -> 530 -> 474 -> NULL, which is the final list.

My code:

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();

typedef struct SinglyLinkedListNode SinglyLinkedListNode;
typedef struct SinglyLinkedList SinglyLinkedList;

struct SinglyLinkedListNode {
    int data;
    SinglyLinkedListNode* next;
};

struct SinglyLinkedList {
    SinglyLinkedListNode* head;
};

SinglyLinkedListNode* create_singly_linked_list_node(int node_data) {
    SinglyLinkedListNode* node = malloc(sizeof(SinglyLinkedListNode));

    node->data = node_data;
    node->next = NULL;

    return node;
}

void print_singly_linked_list(SinglyLinkedListNode* node, char* sep, FILE* fptr) {
    while (node) {
        fprintf(fptr, "%d", node->data);

        node = node->next;

        if (node) {
            fprintf(fptr, "%s", sep);
        }
    }
}

void free_singly_linked_list(SinglyLinkedListNode* node) {
    while (node) {
        SinglyLinkedListNode* temp = node;
        node = node->next;

        free(temp);
    }
}

// Complete the insertNodeAtTail function below.

/*
 * For your reference:
 *
 * SinglyLinkedListNode {
 *     int data;
 *     SinglyLinkedListNode* next;
 * };
 *
 */
//This is the required function which I have written
SinglyLinkedListNode* insertNodeAtTail(SinglyLinkedListNode* head, int data) {
SinglyLinkedListNode *newNode = (SinglyLinkedListNode*)malloc (sizeof(SinglyLinkedListNode));
 SinglyLinkedListNode *p = head;
while(p->next!=NULL){
    p=p->next;
}
newNode->data = data;
newNode ->next = p->next;
p ->next = newNode;
return head;

}


int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    SinglyLinkedList* llist = malloc(sizeof(SinglyLinkedList));
    llist->head = NULL;

    char* llist_count_endptr;
    char* llist_count_str = readline();
    int llist_count = strtol(llist_count_str, &llist_count_endptr, 10);

    if (llist_count_endptr == llist_count_str || *llist_count_endptr != '\0') { exit(EXIT_FAILURE); }

    for (int i = 0; i < llist_count; i++) {
        char* llist_item_endptr;
        char* llist_item_str = readline();
        int llist_item = strtol(llist_item_str, &llist_item_endptr, 10);

        if (llist_item_endptr == llist_item_str || *llist_item_endptr != '\0') { exit(EXIT_FAILURE); }

        SinglyLinkedListNode* llist_head = insertNodeAtTail(llist->head, llist_item);
        llist->head = llist_head;
    }



    char *sep = "\n";

    print_singly_linked_list(llist->head, sep, fptr);
    fprintf(fptr, "\n");

    free_singly_linked_list(llist->head);

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) {
            break;
        }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') {
            break;
        }

        alloc_length <<= 1;

        data = realloc(data, alloc_length);

        if (!line) {
            break;
        }
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';

        data = realloc(data, data_length);
    } else {
        data = realloc(data, data_length + 1);

        data[data_length] = '\0';
    }

    return data;
}

Output: Core was generated by `./Solution'. Program terminated with signal SIGSEGV, Segmentation fault.

Answer 1

You never check head for NULL prior to enumeration of the list. If there is no "there" there, this:

SinglyLinkedListNode* insertNodeAtTail(SinglyLinkedListNode* head, int data) {
    SinglyLinkedListNode *newNode = (SinglyLinkedListNode*)malloc(sizeof(SinglyLinkedListNode));
    SinglyLinkedListNode *p = head;

    // HERE. If head was NULL then so is p, therefore p->next is BAD
    while (p->next != NULL) {
        p = p->next;
    }
    newNode->data = data;
    newNode->next = p->next;
    p->next = newNode;
    return head;
}

There are multiple ways to address this, one simple to understand, one efficient to code. Among the things to consider:

1. Use either a prev-pointer or a pointer-to-pointer solution to acquire the last node in the list.
2. This is C code. Don't cast malloc in C code

One possible solution is the following. Though it is easier to understand what is going on, it takes more code than an alternate solution which I'll show in a moment:

SinglyLinkedListNode* insertNodeAtTail(SinglyLinkedListNode* head, int data)
{
    SinglyLinkedListNode *prev = NULL;
    SinglyLinkedListNode *p = head;
    while (p)
    {
        prev = p;
        p = p->next;
    }

    p = malloc(sizeof *p);
    p->data = data;
    p->next = NULL;

    if (prev)
        prev->next = p;
    else
        head = p;

    return head;
}

An alternative involves using a pointer to pointer, and utilizing the address of pointers within the list itself, rather than walking by pointer-value. It's more difficult to understand, but considerably less code.

SinglyLinkedListNode* insertNodeAtTail(SinglyLinkedListNode* head, int data)
{
    SinglyLinkedListNode **pp = &head;
    while (*pp)
        pp = &(*pp)->next;

    *pp = malloc(sizeof **pp);
    (*pp)->data = data;
    (*pp)->next = NULL;

    return head;
}

Note that if head contains NULL on entry, the loop immediately terminates, pp still holds the address of the head pointer, populates it with a new node, then returns whatever head contains (the new node address). If head did not contain NULL on entry then pp contains the address of the last next pointer in the list (which will contain NULL) and the new node is hung right there. In that case head remains unchanged and the original head is simply returned.

Hope it helps.

Answer 2

If head is NULL, then when your code does SinglyLinkedListNode *p = head;, p is NULL and thus p->next in while loop's condition should throw bad access aka SegFault.