user6820297 user6820297 - 2 months ago 21
C++ Question

Error in merge sorting of linked list

I am trying to do a merge sorting practice on linked list sort and I couldn't figure the reason that the code doesn't work, my compiler doesn't give any useful error message. Can't someone point it out for me? thanks!

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

using namespace std;

struct listnode { struct listnode * next; int key; };

//function prototypes

void seperate(struct listnode * node, struct listnode ** front, struct listnode ** back);

struct listnode * merge(struct listnode * node_1, struct listnode * node_2);

//merge sorted seperated linked list
void mergeSort(struct listnode ** node)
{
struct listnode * head = * node; struct listnode * node_1; struct listnode * node_2;

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

seperate(head, &node_1, &node_2);
mergeSort(&node_1); mergeSort(&node_2);
* node = merge(node_1, node_2);

}

//sort sepearted linked list
struct listnode * merge(struct listnode * node_1, listnode * node_2)
{
struct listnode * return_result = NULL;
if (node_1 == NULL) { return (node_2); }
else if (node_2 = NULL) { return (node_1); }

if (node_1->key <= node_2->key)
{
return_result = node_1; return_result->next = merge(node_1->next, node_2);
}
else { return_result = node_2; return_result->next = merge(node_1, node_2->next); }

return return_result;

}

//function to seperate linked list
void seperate(struct listnode * node, struct listnode ** front, struct listnode ** back)
{
struct listnode * fast; struct listnode * slow;

if (node == NULL || node->next == NULL) { *front = node; * back = NULL; }

else
{
slow = node; fast = node->next;

while (fast != NULL)
{
fast = fast->next;
if (fast != NULL) { slow = slow->next; fast = fast->next; }
}

* front = node; * back = slow->next; slow->next = NULL;

}


}// merge sort of linked list completed



//test functions to push and print the linked list

void push(struct listnode ** head, int data)
{
struct listnode * added_node = (struct listnode * )malloc(sizeof(struct listnode));
added_node->key = data;
added_node->next = (*head);
(*head) = added_node;
}

void printList(struct listnode * node)
{
while (node != NULL)
{
cout << node->key;
node = node->next;
}

}

int main()
{
struct listnode * node1 = NULL;

push(&node1, 3); push(&node1, 30); push(&node1, 23); push(&node1, 1); push(&node1, 0); push(&node1, 9);
mergeSort(&node1);
cout << endl;
printList(node1);

return 0;
}

Answer
if (node_1 == NULL) { return (node_2); }
else if (node_2 = NULL) { return (node_1); }
/// -----------^ this is an assignment here

To Yoda introduce you I will

if (NULL == node_1) { return (node_2); }
else if (NULL=node_2) { return (node_1); }
/// ---------^ still an assignment, 
//   but try it out & C what the compiler has to say