Move Largest Number to the End of Linked List.

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 :

1. If only one node is present in the linked list , then return head.
2. If no node, then print an error message.

• Initialise two pointers : prevnode to point the previous node in the list and temp to point the head node of the list. Both the pointers are of type struct 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 :

1. Separate the head node from the list, make temp to point second node and make prevnode to point head node.
2. Now, make second node as the head node of the list by head = temp.
3. 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 :

1. Traverse the linked list until number is found equal to value of max . If found, then detach that node from the linked list by prevnode->next = temp->next.
2. Create a new node pointing to by pointer newnode and store the value of max into that node using structure member data and store NULL into its address part using structure member next i.e., newnode->data = max; newnode->next = NULL;
3. 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.