c++ - 使用指针对单链表进行排序

Question

我正在尝试通过仅操作指针而不操作键来使用冒泡排序对单向链表进行排序。

下面的代码陷入 for 循环并无限循环。我不明白这是为什么。任何人都可以向我解释为什么找不到列表的末尾吗？

Node* sort_list(Node* head)
{
    Node * temp;
    Node * curr;
    for(bool didSwap = true; didSwap; ) {
            didSwap = false;
            for(curr = head; curr->next != NULL; curr = curr->next) {
                    if(curr->key > curr->next->key) {
                            temp = curr;
                            curr = curr->next;
                            curr->next = temp;
                            didSwap = true;
                    }
                    cout << curr->next->key << endl;
            }
    }
    return head;

如果我更改代码以便交换键(数据)，则该函数可以正常工作，但由于某些原因我无法通过仅操作指针来使其工作。

Answer 1

逻辑错误，您正在使用以下代码创建无限循环 -

temp = curr;
curr = curr->next;
curr->next = temp;

I,e next_of_current 指向 current，所以 curr->next 永远是 curr，永远不会是 NULL；

接下来你应该使用 previous 指针来修复你的列表，因为你的列表可以在一个方向上遍历。所以，想想——如果A->B->C->NULL；然后你让 C 和 B 交换然后新列表将仍然指向 A->B 并且下一次迭代将是错误的......因为你没有修改你的前一个下一个。

所以，另一个实现可能是——

Node* sort_list(Node* head) {
    Node * curr;
    Node * prev;
    for(bool didSwap = true; didSwap; ) {
        didSwap = false;
        prev = head;
        for(curr = head; curr->next != NULL; curr = curr->next) {
                if(curr->key > curr->next->key) {
                        if (head == curr) {
                            head = curr->next;      
                            curr->next = head->next; 
                            head->next = curr; 
                            prev = head;
                        } else {
                            prev->next = curr->next;
                            curr->next = prev->next->next;
                            prev->next->next = curr
                        }
                        didSwap = true;
                } else if (head != curr) {
                    prev = prev->next;
                } 
                //cout << curr->next->key << endl; // <- this may cause crash if curr->next now points to NULL; (i,e last element)
            }
    }
    return head;
}

希望这对您有所帮助，问候。