插入排序链表C++

Question

我正在尝试编写代码来对包含整数的链表进行排序，但根据我用铅笔和纸计算出来的推理，它无法正常工作。它不是遍历列表，而是比较第一对值，删除列表中的第二个值和 returns 列表的其余部分。我的方法代码是：

//typedef Node * ListType;

void insertionSort(ListType &list) {
    ListType p = list;
    Node * curr;
    if(p == NULL || p->next == NULL){
        return;
    }
    while(p != NULL){
        curr = p->next;
        if(curr == NULL){
            break;
        }
        if(p->data > curr->data){
            p->next = curr->next;
            curr->next = p;
        }
        p = p->next;
    }
}

比如说，我从一个列表开始：5 2 3 4 在此列表上调用此方法后得到的输出是：5 3 4

我不喜欢指点。感谢您的帮助！

Answer 1

如果您不使用指针，而是使用指向指针的指针，这种任务的效果会更好。如果新元素单独传递，而不是在列表的开头 "pre-inserted"，它也会更好地工作。

但是，让我们继续吧，新节点已预先插入到列表的开头，您希望将其移动到正确的位置。

然后，它会是这样的：

#include <iostream>

class Node {

public:

    Node *next;

    int data;
};

typedef Node * ListType;

void insertionSort(ListType &list) {
    ListType *p = &list;

    while ( (*p)->next && (*p)->next->data < (*p)->data)
    {
        ListType node= *p;

        *p=node->next;

        node->next=node->next->next;

        (*p)->next=node;

        p= &(*p)->next;
    }
}

int main()
{
    Node *head=0;

    int n;

    while (std::cout << ">>> ", std::cin >> n)
    {
        Node *p=new Node;

        p->data=n;

        p->next=head;
        head=p;

        insertionSort(head);

        for (p=head; p; p=p->next)
            std::cout << p->data << " ";
        std::cout << std::endl;
    }
}

示例结果：

$ ./t
>>> 5
5 
>>> 7
5 7 
>>> 1
1 5 7 
>>> 3
1 3 5 7 
>>> 9
1 3 5 7 9 
>>> 6
1 3 5 6 7 9 
>>> 0
0 1 3 5 6 7 9

这里的技巧是 p 不是指向您要插入的节点的指针，p 是指向要插入的节点的指针。因此，如果您需要 "push" 列表下方的新节点，"previous" 指针是 *p，您现在可以轻松更新它。

尽管乍一看这看起来很混乱，但它远没有跟踪 "previous" 节点那么混乱，您需要更新其下一个指针。所有 if 语句毛球都完全消失了。这就是所有混乱的来源。

此外，如果像我最初提到的那样，新节点未预先插入到列表的开头，并作为单独的指针传递，那么这将变得更容易理解。但是，那是你的出发点，所以...

插入排序链表C++

insertion sort linked list c++

c++

linked-list

insertion-sort

singly-linked-list