我的鏈接列表代碼出現錯誤，任何人都可以幫助我檢查哪裏出錯？

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 - > -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; 
     } 
    } 
}