For a given linked list, you are supposed to write a function that moves the largest number to the end of the list.
Example 1:
Input : 4 6 2 8 1
Output : 4 6 2 1 8
Example 2:
Input : 9 5 1 8 2
Output : 5 1 8 2 9
Steps:
To move the largest number to the end, first you need to write the function that returns the largest number. Store that largest(maximum) number in an integer variable
max.Write the base case :
- If only one node is present in the linked list , then
return
head. - If no node, then print an error message.
Initialise two pointers :
prevnodeto point the previous node in the list andtempto point theheadnode of the list. Both the pointers are of typestruct node.Compare the value of
maxwith each number(data) of the linked list.If the value of
maxis equal to the first data of the linked list :
- Separate the
headnode from the list, maketempto point second node and makeprevnodeto pointheadnode. - Now, make second node as the
headnode of the list byhead = temp. - Traverse the linked list until last node and connect the detached node(to which pointer
prevnodeis pointing) to the last node which contains the largest number of the linked list.
- If the value of
maxequals to other than first data in the list :
- Traverse the linked list until number is found equal to value of
max. If found, then detach that node from the linked list byprevnode->next = temp->next. - Create a new node pointing to by pointer
newnodeand store the value ofmaxinto that node using structure memberdataand storeNULLinto its address part using structure membernexti.e.,newnode->data = max; newnode->next = NULL; - Traverse the linked list until last node and connect the
newnodeto the last node which contains the largest number of the linked list.
- Finally display the new linked list with the largest number at the end.
C program that moves the largest number to the end of linked list.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct node
{
int data;
struct node * next;
};
void displayLL(struct node * head)
{
struct node * temp;
temp = head;
temp=head;
while(temp!=0)
{
printf("%d ",temp->data);
temp = temp->next;
}
}
int large(struct node *head)
{
struct node *temp = head;
int max;
max = INT_MIN;
while(temp != NULL)
{
if(max < temp->data)
{
max = temp->data;
}
temp = temp->next;
}
return max;
}
void largeToEnd(struct node *head)
{
struct node *prevnode, *newnode;
struct node *temp;
int max;
temp = head;
if(head->next == NULL)
{
printf("\n--------------------------------\n");
printf("Linked list with largest number at end : ");
displayLL(head);
exit(0);
}
max = large(head);
if(head->data == max)
{
temp = temp->next;
head->next = NULL;
prevnode = head;
head = temp;
while(temp->next != NULL )
{
temp = temp->next;
}
temp->next = prevnode;
printf("\n--------------------------------\n");
printf("Linked list with largest number at end : ");
displayLL(head);
exit(0);
}
while(temp->data != max)
{
prevnode = temp;
temp = temp->next;
}
prevnode->next = temp->next;
newnode = (struct node *)malloc(sizeof(struct node));
newnode->data = max;
newnode->next = NULL;
temp = head;
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next = newnode;
printf("\n--------------------------------\n");
printf("Linked list with largest number at end : ");
displayLL(head);
}
int main()
{
struct node *head = 0, *newnode, *temp;
int n, choice, newdata, max;
// Create Linked List //
printf("Enter the number of nodes in the list : ");
scanf("%d", &n);
if(n == 0)
{
printf("--------------------------------\n");
printf("Linked list cannot be empty");
exit(0);
}
for(int i = 1; i<=n; i++)
{
newnode = (struct node *)malloc(sizeof(struct node));
printf("Enter the data%d : ", i);
scanf("%d", &newnode->data);
newnode->next = 0;
if(head == 0)
{
head = temp = newnode;
}
else
{
temp->next = newnode;
temp = newnode;
}
}
printf("--------------------------------\n");
printf("Linked list : ");
displayLL(head);
max = large(head);
printf("\n--------------------------------\n");
printf("Largest number of linked list : %d", max);
largeToEnd(head);
}
I own a website www.coderlogs.com where in I write similar blogs so do visit the website for more such blog posts.
Top comments (0)