c++ - 单链表 C++ 的插入排序
问题描述
我得到了一个头文件,它定义了如何创建链表的节点
#ifndef _LISTNODE
#include <cstddef>
#define _LISTNODE
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
#endif
我的任务是创建一个函数,该函数将对链表进行插入排序并按降序对项目进行排序(可以假设链表中没有循环。
函数定义为
ListNode *insertionSortList(ListNode *head)
所以我现在的逻辑是遍历链表,直到发现迭代器当前所在的节点小于它旁边的节点的值。在这种情况下,它获取包含较大数字的节点的值并将其存储在临时指针中。然后我的迭代器位于刚刚放入临时指针的节点之前的数字上,因此该节点现在指向破坏顺序的节点并指向之后的节点。
然后我让另一个迭代器遍历列表,直到它找到它可以使订单工作的位置,然后将存储的节点与临时指针一起放置,并使该节点内的下一个指针指向该节点发现新的迭代器小于它。
如果这个解释有点混乱,我很抱歉,但是当我画出图表时它似乎是有道理的,而且我没有看到我的代码可能会破坏这个逻辑,但是当我用一些测试用例运行它时,它要么不排序,要么有时它不排序并且不打印所有值。
#include <iostream>
#include "ListNode.h"
using namespace std;
ListNode *insertionSortList(ListNode *head)
{
ListNode *temp;
for (ListNode *iterator = head; iterator->next != NULL; iterator = iterator->next) //first iterator to find node that breaks the pattern
{
if (iterator->val >= iterator->next->val) // if it doesn't break the pattern
{
break;
}
else //if it does break the pattern
{
temp = iterator->next; //store pattern breaking node
iterator->next = iterator->next->next; //have linked list skip over this pattern breaking node
for (ListNode *replacementit = head; replacementit->next != NULL; replacementit = replacementit->next) // find place for patteern breaking node
{
if (replacementit->val < temp->val) //if found the right place
{
temp->next = replacementit; //put node into place
break;
}
}
}
}
return head;
}
int main() //test cases
{
ListNode A(5);
ListNode B(6);
ListNode C(10);
ListNode D(21);
ListNode E(25);
ListNode* head = &A;
A.next = &B;
B.next = &C;
C.next = &D;
D.next = &E;
insertionSortList(head);
for (ListNode *print = head; print->next != NULL; print = print->next) //print out sorted Linked List
{
cout << print->val << " ";
}
}
输出
5 10 %
解决方案
您的实现在函数的第一个for
循环内的第一行不正确。insertionSortList
例如 - 如果链表的第一个元素大于或等于链表的第二个元素,您的代码将不再执行 for 循环中的任何行,它将“中断”。您可以使用 list 进行检查2 -> 1 -> 3
。
另外,最后当你打印链表时,它总是不会打印最后一个元素,因为终止条件是错误的。
推荐阅读
- c - wait() 调用会以可预测的顺序执行吗?
- jquery - 使用 Jquery 或 Javascript,如何在滚动时让动画文本一一出现?
- cmake - 使用 WSL 作为 CLion 的工具链时,Cmake 使用了错误的路径
- php - 无法在 wordpress 插件中获取 post_ID
- a-star - MST 和 A* 的旅行推销员?
- bash - 使用位置变量时是否可以解决 SC2001(“看看是否可以使用 ${variable//search/replace}”)?
- json - Tensorflow Serving:期望 arg[0] 为浮点数,但提供了字符串
- angular - vsCode 中缺少 tsconfig.json 文件和实验性装饰器警告
- javascript - 为什么我不能在 JScript 中向 SendKeys 发送 (?
- python - Django:不能在 ModelForm 中使用会话变量