#include #include "sort.h"

// The LinkedListNode constructor. LinkedListNode::LinkedListNode(int value) { this->next = NULL; this->value = value; }

/* The in-place merge sort function for linked lists.

The function sorts the given linked list in place, i.e., no new linked list nodes should be created. It should also run in O(n log n) time as the regular merge sort algorithm. */

LinkedListNode *sortLinkedList(LinkedListNode *list) { LinkedListNode *headptr; LinkedListNode *temp; LinkedListNode *opptr; LinkedListNode *opptr1;

headptr = list; opptr = list; opptr1 = list;

if(list->next == NULL) { return NULL; }

else { int length = 0; while(list->next != NULL) { ++length; list = list->next; }

for(int i=0; i

{

for(int j=0;j< length-i; j++)

{

if(headptr>headptr->next)

{

temp=headptr;

headptr=headptr->next;

head->next=temp;

}

}

}

opptr1 = opptr1->next;

opptr->next = NULL;

sortLinkedList(opptr1); sortLinkedList(headptr);

mergeSortedLinkedLists(headptr,opptr1);

} return NULL; }

/* The merge function for sorted linked lists.

The function takes as inputs two sorted linked lists and outputs the merge of those lists. The merged list must also be sorted. The implementation should use O(1) additional storage. It should reuse the nodes from the lists provided as inputs. */ LinkedListNode *mergeSortedLinkedLists(LinkedListNode *firstList, LinkedListNode *secondList) { LinkedListNode *linkedlist;

if(firstList == NULL) { linkedlist = secondList; secondList = secondList->next; }

else if (secondList == NULL) { linkedlist = firstList; firstList = firstList->next; }

else if(firstList->value <= secondList->value) { linkedlist = firstList; firstList = firstList->next; } else { linkedlist = secondList; secondList = secondList->next; }

return linkedlist; }

// Creates a linked list from the integers in the given array. LinkedListNode *createLinkedList(int *numbers, int length) { if (length == 0) return NULL; LinkedListNode *head, *tail; head = tail = new LinkedListNode(numbers[0]); for (int i = 1; i < length; i++) { LinkedListNode *node = new LinkedListNode(numbers[i]); tail->next = node; tail = node; } return head; }

// Converts a linked list to a human-readable string. string linkedListToString(LinkedListNode *head, string edge) { stringstream output; while (head) { output << head->value; if (head->next) output << edge; head = head->next; } return output.str(); } --------------------------- Header file: ----------------------

#ifndef SORT_H_ #define SORT_H_

using namespace std;

// The linked list node struct struct LinkedListNode { LinkedListNode *next; int value;

LinkedListNode(int); };

// Sorting functions LinkedListNode *sortLinkedList(LinkedListNode *);

LinkedListNode *mergeSortedLinkedLists(LinkedListNode *, LinkedListNode *);

// Miscellaneous functions LinkedListNode *createLinkedList(int *, int);

string linkedListToString(LinkedListNode *, string edge);

#endif /* SORT_H_ */

i need help coz the two functions i'm supposed to write are not giving me the right results.

1. LinkedListNode *sortLinkedList(LinkedListNode *list); 2. LinkedListNode *mergeSortedLinkedLists(LinkedListNode *firstList, LinkedListNode *secondList); 

Remarks:

For the purpose of this lab, a linked list node holds an int value. Please refer to sort.h file for the definition of the LinkedListNode struct that represents a singly-linked list node.

The sortLinkedList function is the starting point of the merge sort algorithm. This function takes a pointer to the first node of a singly-linked list, sorts the linked list in-place, and returns a pointer to the first node of the sorted linked list. The pseudocode of this method is,

Break the given linked list in half,

Recursively sort the two halves,

Merge the sorted halves using mergeSortedLinkedLists function,

Return a pointer to the starting node of the merged linked list.

The mergeSortedLinkedLists function takes as input pointers to the first nodes of two sorted singly-linked lists, merges the two sorted linked lists into one, and returns a pointer to the first node of the merged linked list. You should mimic the merge algorithm of the regular merge sort algorithm. But, keep in mind to reuse the nodes in the input linked lists instead of allocating extra storage for the resulting linked list.