我的链表代码有错误，有人能帮我检查哪里错了吗

Question

这是我的类中的一个小的链表挑战，我们需要定义一个函数

void restoreSorted(intListEntry * &)

其中intListEntry是一个结构

struct intListEntry {
    int i;   // The int value we want to store in this entry
    intListEntry *next;   // Address of the next entry in the list
};

该参数是一个整数链表的头，该链表按非递减顺序排序，但有一个条目不合适。该函数应将列表恢复为非递减排序。例如，作为自变量给出；head-->-12-->-12-->0-->-1-->12-->122，从restoreSorted（）返回时，列表应为：head-->-12->-12-->-1-->0-->12-->122。

这是我的代码：

void restoreSorted(intListEntry * &root) {
    intListEntry *conductor = root;
    intListEntry *checker;
    while (conductor->next != NULL) {
        if (conductor->i > conductor->next->i) {    //detect which one is out of place
            checker = conductor;
            intListEntry *checker2 = conductor->next;
            int temp;
            while (checker->i > checker2->i) {
                temp = checker->i;            //start of swapping value 
                checker->i = checker2->i;     //until it is in the right order
                checker2->i = temp;
                checker = checker2;
                checker2 = checker2->next;
            }
            break;
        }
        conductor = conductor->next;
    }

然而，有五个测试用例，我只通过了其中一个。我一遍又一遍地检查它，仍然在我的代码中找不到任何错误。

Answer 1

在这些注释的帮助下，我终于调试了我的代码，并使用不同的方法制作了两个版本。

第一个是使用我原来的方法-气泡排序：

void restoreSorted( intListEntry * &root ){
    int length = 0;
    intListEntry *current = root;
    intListEntry *prev = NULL;
    int t = 0;
    while (current != NULL){
        length++;
        prev = current;
        current = current -> next;
    }
    current = root;
    prev = NULL;
    for (int i = 0; i < length; i++){
        for (int j = 0; j < length-1 ; j++){
            if (prev == NULL){
                prev = current;
                current = current->next;
            }
            if (current->i < prev->i){
                t = prev->i;
                prev->i = current->i;
                current->i = t;
                current = current->next;  
            } else {
                prev = current;
                current = current->next;
            }
            if (current == NULL) break; 
        }
        current = root;
        prev = NULL;
    }
}

第二种是使用插入方法：

void restoreSorted(intListEntry * &root) {
    intListEntry *conductor = root;
    intListEntry *behind = root;
    intListEntry *checker;
    if (conductor != NULL || conductor->next != NULL) {
        while (conductor->next != NULL) {
            if (conductor->i > conductor->next->i) {
                checker = conductor;
                intListEntry *checker2 = conductor;
                if (checker2->next->next == NULL) {
                    int temp = checker->i;
                    checker->i = checker2->next->i;
                    checker2->next->i = temp;
                    break;
                } else {
                    while (checker->i > checker2->next->i && checker2->next != NULL) {
                        checker2 = checker2->next;
                    }
                    if (checker->i > checker2->i && checker2->next == NULL) {
                        behind->next = checker->next;
                        checker2->next = checker;
                        checker->next = NULL;
                    } else if (checker->i < checker2->next->i) {
                        behind->next = checker->next;
                        conductor = checker2->next;
                        checker2->next = checker;
                        checker->next = conductor;
                        break;
                    }
                }
            }
            behind = conductor;
            conductor = conductor->next;
        }
    }
}