单链表C++的插入排序

Question

我得到了一个头文件，它定义了如何创建链接列表的节点

#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 % 

Answer 1

您的实现在insertionSortList函数的第一个for循环内的第一行不正确。

例如，如果链表的第一个元素大于或等于链表的第二个元素，那么您的代码将不会在For循环中执行更多的行，它将"中断"。您可以查看列表2 -> 1 -> 3。

此外，最后当您打印链表时，它总是不会打印最后一个元素，因为终止条件有问题。