排序单链表的指针(Sorting a Singly Linked List With Pointer

我试图使用排序冒泡排序通过操纵只有指针，没有密钥的单向链表。

以下卡在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指向电流，从而curr->未来永远是CURR也永远不会是NULL;

接下来，你应该使用前的指示来修复您的列表中，因为您的清单可在单一方向上运行。 所以，想想 - 如果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;
}

希望这有助于问候。

Answer 2:

你有以下的问题：

让你列表具有三个成员： ptr1->ptr2->ptr3 。 交换之前，你有以下指针设置： curr=ptr1; curr->next=ptr2; curr->next->next=ptr3 curr=ptr1; curr->next=ptr2; curr->next->next=ptr3 curr=ptr1; curr->next=ptr2; curr->next->next=ptr3 。 当您执行掉期收到curr=ptr2; curr->next=ptr1; curr->next->next=ptr2 curr=ptr2; curr->next=ptr1; curr->next->next=ptr2 curr=ptr2; curr->next=ptr1; curr->next->next=ptr2 。

例如，你失去了PTR3。 您需要更改内部循环的代码如下：

temp = curr;
temp->next = curr->next->next;    // Save ptr3
curr = curr->next;
curr->next = temp;
didSwap = true;

Answer 3:

要交换的领域有value 。 但是，如果您交换node ，则next字段将发生变化，这个问题变得稍微复杂一点，你需要保持next领域的权利。 总之，变化value是一个简单的和好方法。

Answer 4:

node *sorted_list(node *head) {
    node *index1,*index2;
    for(index1=head;index1->next!=NULL;index1=index1->next) {
        for(index2=index1->next;index2!=NULL;index2=index2->next) {
            if(index1->data>index2->data) {
                int temp=index1->data;
                index1->data=index2->data;
                index2->data=temp;
            }
        }
    }
    return head;
}

文章来源: Sorting a Singly Linked List With Pointers