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 :
prevnode
to point the previous node in the list andtemp
to point thehead
node of the list. Both the pointers are of typestruct node
.Compare the value of
max
with each number(data) of the linked list.If the value of
max
is equal to the first data of the linked list :
- Separate the
head
node from the list, maketemp
to point second node and makeprevnode
to pointhead
node. - Now, make second node as the
head
node of the list byhead = temp
. - Traverse the linked list until last node and connect the detached node(to which pointer
prevnode
is pointing) to the last node which contains the largest number of the linked list.
- If the value of
max
equals 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
newnode
and store the value ofmax
into that node using structure memberdata
and storeNULL
into its address part using structure membernext
i.e.,newnode->data = max; newnode->next = NULL;
- Traverse the linked list until last node and connect the
newnode
to 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)