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