sorting - C ++链表合并排序不断丢失节点
问题描述
我在对链表进行合并排序时遇到问题。出于某种原因,一些节点不断与列表断开连接。主要问题似乎来自多个条件跳转,因为诸如1 4 2 3
已排序的列表(尽管有 6 个条件跳转)同时4 2 3 1
丢失了除持有值 4 的节点之外的所有节点。我的代码基于来自tutorialspoint.com的代码。
class Node {
public:
int val;
Node *next;
};
class Linked_list {
private:
unsigned int length;
Node *head;
//desc: sorts in ascending order then merges two linked lists
//param: Node*, the lists being sorted
Node* Linked_List::merge_lists_ascend(Node* ll1, Node* ll2) { //function for merging two sorted list
Node* newhead = NULL;
if(ll1 == NULL)
return ll2;
if(ll2 == NULL)
return ll1;
//recursively merge the lists
if(ll1 -> val <= ll2 -> val) {
newhead = ll1;
newhead -> next = merge_lists_ascend(ll1->next,ll2);
}
else {
newhead = ll2;
newhead -> next = merge_lists_ascend(ll1,ll2->next);
}
return newhead;
}
//desc: splits a linked list into two lists
//param: Node*, the list being split; Node**, the two lists that will be filled
//by the split list
void Linked_List::splitList(Node* start, Node** ll1, Node** ll2) {
Node* slow = start;
Node* fast = start -> next;
while(fast != NULL) {
fast = fast -> next;
if(fast != NULL) {
slow = slow -> next;
fast = fast -> next;
}
}
*ll1 = start;
*ll2 = slow -> next;
//spliting
slow -> next = NULL;
}
//desc: recursive function that runs through the splitting, sorting and merging
//param: Node**, the starting node
Node* Linked_List::merge_sort_ascend(Node* start) {
Node* head = start;
Node* ll1;
Node* ll2;
//base case
if(head == NULL || head->next == NULL) {
return head;
}
splitList(head,&ll1,&ll2); //split the list in two halves
//sort left and right sublists
ll1 = merge_sort_ascend(ll1);
ll2 = merge_sort_ascend(ll2);
//merge two sorted list
start = merge_lists_ascend(ll1,ll2);
return start;
}
解决方案
当你merge_sort_ascend
递归调用时,你会忽略它的返回值。该返回值很重要。
推荐阅读
- excel - 如何以角度绘制excel样式的数据条?
- oracle - 链接到文件服务器 ApEx
- angular - 转到页面选项功能缺少 PrimeNG 分页器
- php - 我想将数据插入到 codigIgnitor 中具有相同 id 的两个表中
- javascript - getElementById 检查是否包含维度
- docker - 与 2 个同行创建组织
- python - 使用 Python 从下载文件夹中删除文件
- javascript - 如果我使用 webpack,是否需要实时主机服务器上的 node_modules 文件夹?
- c - 无法将 .txt 文件重定向到标准输入
- python - os.walk-ing 遍历目录以读取和写入所有 CSV