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

Please find all the code explanations within the code itself as comments.

We have added some snippets of our code for clarification of some points. The full code can be found at the end.

We are given the definition of the node structure in the problem statement:

// the definition of the structure as given in the problem statement
struct node { 

        int item; 
        node* next; 

        node(int x, node* t) { 
                item = x; 
                next = t; 
        } 
};

We need to design a function moveMaxToLast(link h) which interchanges the item values of the node with maximum item value and the last node of the linked list.

Therefore, we need to do this (according to the problem statement) :

1. Find the link to the last node of the linked list. (we will create a helper function for this)

2. Find the link to the maximum item value node of the linked list. (we will create a helper function for this)

To get the link of the last node of our linked list, we need to traverse till the end of our linked list, therefore, the running time complexity for this operation will be:

Similarly, to get the link of the maximum item value node, again, we need to traverse till the end of our linked list, therefore, the running time complexity for this operation will be again:

Therefore, the overall running time of our algorithm will be:

(

Please note that to test our code, we have used a very simple main function implementation for clarity and we have not considered this for our main function(although, it's running time complexity is the same).

We have created the linked list by adding new nodes at the front of the list. Also, because in the constructor, we need to provide the next link of the new node we are creating, we can easily add the new nodes at the front of the list by using the next to the new node as the head of the current list. Have a look at the code snippet of the main function.

link head = NULL;

// first node 
head = new node (1, NULL);

// just for testing the code we have written, 
// we are creating a linked list in a random fashion

// we will push the new nodes to the front of the existing list
// we will use the constructor of the linked list for that

// because everytime we are pushing in the front
// the head of the linked list will change 

// second node 
head = new node (5, head);

// third node 
head = new node (10, head);

// forth node 
head = new node (7, head);

// fifth node
head = new node (3, head);

)

Here is the full code:

# include <iostream>
# include <climits>
using namespace std;

// the definition of the structure as given in the problem statement
struct node { 

        int item; 
        node* next; 

        node(int x, node* t) { 

                item = x; 
                next = t; 
        } 
};

// the typedef statement as provided in the problem statement
typedef node* link;

// this is a helper function used to find the link to the node 
// with maximum value in the linked list 
link findMaxValueNode (link h) {

        // we will create a link to traverse the list
        link ptr = h;

        // we will save the link with maximum value 
        // we will initialize it with the head of the list
        link maxValueNode = h;
                
        // we will traverse the list until we hit the NULL
        while (ptr != NULL) {
                
                // check if the list item value is greater than 
                // our maxValueNode item value

                // if yes, then, update the maxValueNode link
                if ((ptr -> item) > (maxValueNode -> item)) {
                        maxValueNode = ptr;     
                }

                // after checking the node, we will update 
                // the ptr link to point to the next node
                ptr = ptr -> next;
        }

        return maxValueNode;
}


// this is a helper function used to find the link to the last node 
// in the linked list 
link findLastNode (link h) {
                
        // we will save the link to the last node in this variable
        link lastNode = h;

        // because, the last node of the linked list will have its next equal to NULL
        // we will traverse until the next link is NULL
        while (lastNode -> next != NULL) {
                // the lastNode link to point to the next node
                lastNode = lastNode -> next;
        }

        return lastNode;
}

// this function will interchange the maximum value node
// and the last node
void moveMaxToLast(link h) {

        // get the link to the last node
        link lastNode = findLastNode (h);

        // get the link to the maximum item value node
        link maxItemValueNode = findMaxValueNode (h);

        // swap the item values present in both the nodes
        swap (lastNode -> item, maxItemValueNode -> item);
}

void print (link head) {
                
        // create a link to traverse the list
        link ptr = head;

        // traverse until NULL is encountered
        while (ptr != NULL) {

                // print the list
                cout << ptr -> item << " ";

                // update the ptr link to point to the next node
                ptr = ptr -> next;
        }
}

int main (void) {
                
        link head = NULL;

        // first node 
        head = new node (1, NULL);

        // just for testing the code we have written, 
        // we are creating a linked list in a random fashion

        // we will push the new nodes to the front of the existing list
        // we will use the constructor of the linked list for that

        // because everytime we are pushing in the front
        // the head of the linked list will change 

        // second node 
        head = new node (5, head);

        // third node 
        head = new node (10, head);

        // forth node 
        head = new node (7, head);

        // fifth node
        head = new node (3, head);

        // printing the linked list before the call to moveMaxToLast() function
        cout << "\n\nLinked list before the moveMaxToLast() call: ";
        print (head);

        // interchange the item values of the node with maximum item value and the last node of the linked list
        moveMaxToLast (head);

        cout << "\nLinked list after the moveMaxToLast() call: ";
        // printing the linked list after the call to moveMaxToLast() function
        print (head);
        cout << "\n\n";


        return 0;
}
                

Please refer to the screenshots of the code for understanding the indentation of the code.

Let's take a look at the input-output:

Note the change in position of the max item value node (10) and the last node (1).