2
\$\begingroup\$

Problem Summary:

Given a singly linked list, remove all the nodes which have a greater value on right side.

Example: The list 12->15->10->11->5->6->2->3->NULL should be changed to 15->11->6->3->NULL. Note that 12, 10, 5 and 2 have been deleted because there is a greater value on the right side.

Full problem statement

My logic follows Method 2 mentioned in the solution to that problem.

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

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

void printList (struct node* head)
{
    struct node* current;
    for (current = head; current != NULL; current = current->next)
        printf ("%d\n",current->data);
}

void appendNode (struct node** headRef, int data)
{
    struct node* newNode = malloc(sizeof(struct node));

    newNode->data = data;
    newNode->next = *headRef;
    *headRef = newNode;
}   

void reverseList (struct node** head)
{
    struct node* past = NULL;
    struct node* present;
    struct node* future;

    for (present = *head; present != NULL; )
    {
        future = present->next;
        present->next = past;
        past = present;
        present = future;
    }
        *head = past;
}

void removeGreater (struct node** head)
{
    struct node* current;
    struct node* prev;
    int max;

    if (*head != NULL)
    {
        max = (*head)->data;
        prev = *head;
        for (current = (*head)->next; current != NULL;)
        {

            if (current->data >= max)
            {
                max = current->data;
                prev = current;
                current = current->next;
            }
            else
            {
                if (current->next != NULL)
                {
                    struct node* temp = current->next;
                    current->data = temp->data;
                    current->next = temp->next;
                    free (temp);
                }
                else
                {
                    prev->next = NULL;
                    free (current);
                    break;
                }
            }
        }
    }
}   

int main(void)
{

    struct node* head = NULL;
    struct node* tail;
    struct node* current;

    int input,num,num1;

    printf ("Enter no. of inputs \n");
    scanf ("%d",&num);
    num1 = num;
    printf ("\n");
    printf ("Enter the numbers\n");

    do
    {
        scanf("%d",&input);
        if (head == NULL)
        {
            appendNode (&head, input);
            tail = head;
        }
        else
        {
            appendNode (&tail->next, input);
            tail = tail->next;
        }   
        num--;
    } while (num > 0);

    printf ("\n Before Reversing :\n");
    printList (head);

    reverseList(&head);

    printf ("\n After Reversing :\n");
    printList (head);

    removeGreater (&head);
    printf ("\n After Removing :\n");
    printList (head);

    reverseList(&head);
    printf ("\n Final Output :\n");
    printList (head);


    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I want to downvote the page where you found the problem :-). The problem is not stated very well. (1) linked list don't have right sides (2) the last line of Example "a" is wrong, 11 is missing. (3) The examples are not very instructive. if you remove an element of a linked list if it points to a higher element, you get the right output. (This was my understanding of the problem before I read the solution) (4) The short solutions are placed immediately after the examples. It is almost not possible not to read them. \$\endgroup\$ – miracle173 Aug 29 '14 at 6:36
2
\$\begingroup\$

In appendNode(), you have to provide a pointer to node to sizeof() and typecast its return value to struct node*:

void appendNode (struct node** headRef, int data)
{
    struct node* newNode = (struct node*)malloc(sizeof(struct node*));

    newNode->data = data;
    newNode->next = *headRef;
    *headRef = newNode;
}
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! There is indeed a bug in the call to malloc(), but you haven't stated the problem exactly in your answer. \$\endgroup\$ – 200_success Aug 29 '14 at 4:38
0
\$\begingroup\$

It hink that your removeGreater function can be simplified:

    void removeGreater (struct node** head)
    {
        struct node *current = *head;
        while (current)
        {
            if (current->next && current->data > current->next->data)
            {
               struct node* remove = current->next;
               current->next = remove->next;
               free(remove);
            }
            else
            {
               current = current->next;
            }
        }
    }   
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.