Linked list: remove all nodes whose next element has a larger value

Question

I'd like to remove in a linked list all the nodes that have a greater value to their right.

Input: 10 -> 12 -> 15 -> 20 -> 5 -> 16 -> 25 -> 8 -> NULL
Expected output: 20 -> 25 -> 8 -> NULL
Actual Output: 20 -> 25 ->

Kindly help me resolve the bug.

#include <stdlib.h>
#include <stdio.h>

 struct node{
    int data;
    struct node *ptr;
}*start=NULL, *t, *last=NULL;

int i=0;

int main() {
    //creation
    int size;
    printf("Enter size:");
    scanf("%d", &size);

    while (size--) {
        t = (struct node *) malloc(sizeof(struct node));
        printf("Enter list:");
        scanf("%d", &(t->data));
        t->ptr = NULL;
        if (start == NULL) {
            start = t;
        } else
            last->ptr = t;
        last = t;
    }

    //display
    printf("\n");
    t = start;
    do {
        printf("%d->", t->data);
        t = t->ptr;
    } while (t != NULL);
    printf("NULL\n");

    //main objective
    struct node *t1,*t2;
    t1=start;
    t2=t1->ptr;
    t=start;
    for(t=start;t!=NULL;t=t->ptr){
        if(t1->data>t2->data||t->ptr==NULL){
            printf("%d->", t->data);
        }
        t1=t1->ptr;
        t2=t2->ptr;
    }
    printf("NULL\n");

    return 0;
}

score 0 · Answer 1 · answered Oct 20 '19 at 18:33

You are facing Core Dump/Segmentation fault which is a specific kind of error caused by accessing memory that “does not belong to you.”

The iteration before the last one, you're setting t1 <- 8 & t2 <- NULL. So when you enter the last iteration, you check t1->data with t2->data with in if(), which resutls in accessing NULL->data (you're not allowed).

To fix this, you need to add some extra condition to handle this case.

ggorlen · Accepted Answer · 2019-10-20T19:22:34.793

You can fix the segmentation fault due to illegal memory access by verifying that t2 is not null before attempting to dereference the pointer. This version runs clean after adding guards to t2:

for (t = start; t; t = t->ptr) {
    if (!t2 || (t1 && t1->data > t2->data)) {
        printf("%d->", t->data);
    }

    t1 = t1->ptr;

    if (t2) {
        t2 = t2->ptr;
    }
}

Although this shows the correct output, the list isn't actually modified, so we're simply producing a side effect, rendering the routine useless for manipulating the data in memory for other purposes.

A few additional suggestions:

There's no need for global variables in this program.
Avoid unnecessary variables (t and t1 are basically the same, so it's easy to remove one of these. We can also remove t2 and use t->ptr instead).
Give variables descriptive names.
Use spacing around operators.
Separate logical chunks of code into separate functions rather than adding comments in main to delimit them.
Free allocated memory when finished with it.
No need to cast the result of malloc.

Here's a version that modifies the list in-place and implements the above points:

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *ptr;
};

void remove_right_larger(struct node **head) {    
    for (struct node *curr = *head, *prev = NULL;
         curr; curr = curr->ptr) {
        if (curr->ptr && curr->data < curr->ptr->data) {
            if (prev) {
                prev->ptr = curr->ptr;
            }
            else {
                *head = curr->ptr;
            }

            free(curr);
        }
        else {
            prev = curr; 
        }
    }
}

void print_list(struct node *head) {
    for (; head; head = head->ptr) {
        printf("%d->", head->data);
    }

    puts("NULL");
}

void free_list(struct node *head) {
    while (head) {
        struct node *tmp = head;
        head = head->ptr;
        free(tmp);
    }
}

struct node *input_list() {
    struct node *start = NULL;
    struct node *last = NULL;
    int size;
    printf("Enter size: ");
    scanf("%d", &size);

    while (size--) {
        struct node *tmp = malloc(sizeof(*tmp));
        tmp->ptr = NULL;
        printf("Enter list: ");
        scanf("%d", &(tmp->data));

        if (start) {
            last->ptr = tmp;
        } 
        else {
            start = tmp;
        }

        last = tmp;
    }

    return start;
}

int main() {
    struct node *head = input_list();
    print_list(head);
    remove_right_larger(&head);
    print_list(head);
    free_list(head);
    return 0;
}

Linked list: remove all nodes whose next element has a larger value

2 Answers2