#include <sstream> #include \"sort.h\" // The LinkedListNode constructor. Linked
ID: 3678583 • Letter: #
Question
#include <sstream>
#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<length;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.
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.
Explanation / Answer
The function LinkedListNode *mergeSortedLinkedLists(LinkedListNode *firstList, LinkedListNode *secondList) need not be changed.
The modified code of the function LinkedListNode *sortLinkedList(LinkedListNode *list) is below:
LinkedListNode *sortLinkedList(LinkedListNode *list) {
LinkedListNode *headptr;
//LinkedListNode *temp;
LinkedListNode *opptr;
LinkedListNode *opptr1;
/* Base case */
if (list->next == NULL)
{
Return NULL;
}
struct node* fast;
struct node* slow;
if (*headptr==NULL || *headptr->next==NULL)
{
/* length < 2 cases */
*opptr = *headptr;
*opptr1 = NULL;
}
else
{
slow = *headptr;
fast = *headptr->next;
/* Advance 'fast' two nodes, and advance 'slow' one node */
while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}
/* 'slow' is before the midpoint in the list, so split it in two
at that point. */
*opptr = *headptr;
*opptr1= slow->next;
slow->next = NULL;
}
/* Recursively sort the sublists */
sortLinkedList(opptr1);
sortLinkedList(headptr);
/* answer = merge the two sorted lists together */
mergeSortedLinkedLists(headptr,opptr1);
}
return NULL;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.