Question

The following is how we define a linear linked list node: (USE IT IN QUESTIONS 1 & 2)

    struct node

   { int item; node* next;    

       node(int x, node* t)

         { item = x; next = t; }

    };

    typedef node* link;

Write a C++ function void moveMaxToLast(link h) that takes as a parameter a link to the head of a linked list L. After this function performs, L still contains the same item values with the following change in order of values: the function moves the maximum value in the item field to the last in L. You can assume (it is given) that L has at least two nodes, and item values in all nodes are distinct.

Hint: This can be done by finding a link to the node whose item field is maximum in L, and finding a link to the last node. Then the item values in both nodes can be swapped (interchanged). Note that this does not require any delete or insert of nodes.

void moveMaxToLast(link h)

{

}

Answer 1

#include <iostream>

using namespace std;

struct node

{

    int item;

    node *next;

    node(int x, node *t)

    {

        item = x;

        next = t;

    }

};

typedef node *link;

void moveMaxToLast(link h)

{

    // first find maximum node

    link max = h;

    // iterate over given list

    while (h->next != nullptr)

    {

        // move to next node

        h = h->next;

        // if current node is greater than max

        if (h->item > max->item)

        {

            // set max to current node

            max = h;

        }

    }

    // now swap value of max with value of h, which points to last node

    int temp = max->item;

    max->item = h->item;

    h->item = temp;

}

.