This is a C++ problem: Consider a linked list made of nodes of the following str

Question

This is a C++ problem:

Consider a linked list made of nodes of the following struct:

struct ListNode

{

   double data;

   ListNode* next;

}

Assume that each ListNode in a linked list has an index equal to its distance (in number of links) from the head node. For example, for a linked list of length 4, the head node will have index 0, the second node will have index 1, the third node will have index 2, and the tail node will have index 3. Note the similarity with the way that arrays are indexed.

Write a function with the following prototype:

ListNode* swapWithHead(ListNode* head, int index);

The function should accept a pointer to the head of a list as well as an index. It should locate the node at the given index and swap it with the head node. If the swap is successful, the function should return a pointer to the new head. If the swap is unsuccessful (i.e., there is no node at the given index), the function should return the original head pointer.

Write a function that takes an arbitrary linked list and sorts it so that the data values in the list are in alphabetical order. Your prototype should be:

void sortList(ListNode* head);

As a hint, you can use the function that you wrote for the beginning of this problem as well as the selection sort algorithm.

Explanation / Answer

ListNode* swapWithHead(ListNode* head, int index)

{ struct node* current = head;

    int count = 0; /* the index of the node we're currently

                  looking at */

    while (current != NULL)

    {

       if (count == index)

          return(current->data);

       count++;

       current = current->next;

// Change head pointer to point to next node
       head = head->next;

}

    }

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.