I am trying to make an inplace merge sort. Following are the codes that i wrote

Question

I am trying to make an inplace merge sort. Following are the codes that i wrote for the program. The skeleton was made i only have to write codes for LinkedListNode *sortLinkedList(LinkedListNode *list) and LinkedListNode *mergeSortedLinkedLists(LinkedListNode *firstList, LinkedListNode *secondList) functions. Based on me the program suppose to work but it still has some errors, not syntax wise but the logic wise. The pre conditions are written on the top of these function. Can some one help me with writing codes for these two functions and let me know where am i making mistakes?

#include <sstream>
#include <iostream>
#include "sort.h"
using namespace std;
// 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) {
// TODO
LinkedListNode *headptr;
LinkedListNode *tailptr;
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;
}

int midpoint = length/2;

for(int i = 0; i < midpoint; i++)
{
opptr = opptr->next;
opptr1 = opptr1->next;
}

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) {
// TODO
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();
}

______________________________________________________________________________________

The following is the 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_ */

Explanation / Answer

LinkedListNode *sortLinkedList(LinkedListNode *list) {
// TODO
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;
}

I think you did mistake at sorting of list, here we have to swap the nodes.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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