listInsertionSort() /* * This function should perform an insertion sort on the l

Question

listInsertionSort()

/*
* This function should perform an insertion sort on the list whose head is
* provided as the function's argument, so that the values in the list are
* sorted in ascending order, starting at the head.
*
* The sort should be done without allocating any new Link structs or any
* other auxiliary data structures.
*
* Return a pointer to the new head of the list.

*/

reverseList()

/*
* This function should iteratively reverse the list whose head is provided
* as the function's argument.
*
* The reversal must be done totally in place, i.e. you may not allocate any
* new Link structs or any other auxiliary data structures.
*
* Return a pointer to the new head of the list.
*/

reverseListRecursive()

/*
* Write this function for extra credit. It should do the exact same thing
* as reverseList() above, except it should do it recursively instead of
* iteratively (i.e. no loops allowed).
*
* Again, you may not allocate any new Link structs or any other auxiliary
* data structures. You may, however, define an auxiliary function to help
* you do the recursion.
*
* Return a pointer to the new head of the list.
*/

1 #irnder LINKEDLIST HE 2 #define LINKEDLIST H 4 #define TYPE int 6 Single link structure 7 struct Link TYPE alue struct Linke next 10 12 struct Linke listInsertionsort struct Linke head Linke reverseList struct Linke head 14 struct Linke reverselistRecursive (struct Linke head 15 #endif 16

Explanation / Answer

Here are the implementation details for you:

#include <iostream>
#include "SinglyLinkedList.h"
struct Link* listInsertionSort(struct Link* head)
/*
* This function should perform an insertion sort on the list whose head is
* provided as the function's argument, so that the values in the list are
* sorted in ascending order, starting at the head.
*
* The sort should be done without allocating any new Link structs or any
* other auxiliary data structures.
*
* Return a pointer to the new head of the list.
*/
{
struct Link *newList = NULL;
struct Link *current = head;
while (current != NULL)
{
struct Link *next = current->next;
struct Link* newCurrent;
if (newList == NULL || newList->value >= current->value)
{
current->next = newList;
newList = current;
}
else
{
newCurrent = newList;
while (newCurrent->next!=NULL && newCurrent->next->value < current->value)
newCurrent = newCurrent->next;
current->next = newCurrent->next;
newCurrent->next = current;
}
current = next;
}
head = newList;
return head;
}
struct Link* reverseList(struct Link* head)
/*
* This function should iteratively reverse the list whose head is provided
* as the function's argument.
*
* The reversal must be done totally in place, i.e. you may not allocate any
* new Link structs or any other auxiliary data structures.
*
* Return a pointer to the new head of the list.
*/
{
struct Link* prev = NULL;
struct Link* current = head;
struct Link* next;
while (current != NULL)
{
next = current->next;
current->next = prev;   
prev = current;
current = next;
}
head = prev;
return head;
}
struct Link* reverseListRecursive(struct Link* head)
/*
* Write this function for extra credit. It should do the exact same thing
* as reverseList() above, except it should do it recursively instead of
* iteratively (i.e. no loops allowed).
*
* Again, you may not allocate any new Link structs or any other auxiliary
* data structures. You may, however, define an auxiliary function to help
* you do the recursion.
*
* Return a pointer to the new head of the list.
*/
{
struct Link* first;
struct Link* rest;

if (head == NULL)
return NULL;   
first = head;
rest = first->next;
if (rest == NULL)
return NULL;   
reverseListRecursive(rest);
first->next->next = first;
  
first->next = NULL;
head = rest;
return head;
}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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