鏈接列表的遞歸遞增和遞歸降序功能

Question

這是一項家庭作業，我已經編寫了大部分代碼，唯一無法弄清楚的是我必須有一個遞歸函數來排序鏈接列表按升序排列，遞歸函數按降序排列鏈接列表。我很迷茫。

這是我的整個代碼。

using namespace std; 

struct ListNode; 
typedef ListNode* ListPtr; 

struct ListNode 
{ 
    int number; 
    ListPtr next; 

    ListNode(int value, ListPtr ptr = NULL) 
    { 
     number = value; 
     next = ptr; 
    } 
}; 

char Menu(); 
void Add(ListPtr &, int); 
void Delete(ListPtr &, int); 
void Ascend(ListPtr &); 
void Descend(ListPtr &); 
void Print(ListPtr &); 
void DeleteList(ListPtr &); 

int main() 
{ 
    ListPtr head = NULL; 
    char answer; 
    int input; 

    answer = Menu(); 
    while(answer != 'Q') 
    { 
     if(answer == 'A') 
     { 
      cout << "Please enter in an integer: "; 
      cin >> input; 
      Add(head, input); 
     } 
     else if(answer == 'D') 
     { 
      cin >> input; 
      Delete(head, input); 
     } 
     else if(answer == 'P') 
     { 
      Ascend(head); 
     } 
     else if(answer == 'O') 
     { 
      Descend(head); 
     } 
     else if(answer == 'N') 
     { 
      Print(head); 
     } 
     else 
     { 
      cout << "Incorrect input, please try again.\n"; 
     } 

     answer = Menu(); 
    } 

    DeleteList(head); 
    return 0; 
} 

char Menu() 
{ 
    char uinput; 

    cout << "Please enter in one of the following:\n"; 
    cout << "A: Add an item to the end of the list.\n"; 
    cout << "D: Delete an item from the list.\n"; 
    cout << "P: Print the list in ascending order.\n"; 
    cout << "O: Print the list in descending order.\n"; 
    cout << "N: Display the number of items in the list.\n"; 
    cout << "Q: Quit.\n"; 

    return toupper(uinput); 
} 

void Add(ListPtr &start, int item) 
{ 
    if(start->number > item || start == NULL) 
     start = new ListNode(item, start); 
    else 
     Add(start->next, item); 
} 

void Delete(ListPtr &start, int item) 
{ 
    if(start != NULL) 
    { 
     if(start->number == item) 
      ListPtr cur = start; 
     start = start->next; 
     delete cur; 
    } 
    else 
    { 
     Delete(start->next, item); 
    } 
} 

void Ascend(ListPtr &start) 
{ 

} 

void Descend(ListPtr &start) 
{ 

} 

void Print(ListPtr &start) 
{ 
    ListPtr cur = start; 
    int count = 0; 

    if(cur == NULL) 
    { 
     cout << "The list is empty.\n"; 
    } 
    else 
    { 
     if(cur != NULL) 
     { 
      if(count % 10 == 0) 
       cout << endl; 
      cout << setw(5) << cur->number; 
      cur = cur->next; 
      count++; 
     } 
    } 
    cout << endl; 
} 


void DeleteList(ListPtr &start) 
{ 
    if(start != NULL) 
    { 
     DeleteList(start->next); 
     cout << "Deleting item " << start->number << endl; 
     delete start; 
    } 
} 

Answer 1

對於遞歸部分，一種方法是將列表遞歸劃分成兩個列表，左和右，直到列表大小減小到1（或零），在該情況下，遞歸函數只是返回列表，否則它會在遞歸函數中跟隨代碼合併返回的左列表和右列表，並返回合併列表。

您是否學過如何將鏈表分成兩個列表？通常這是使用兩個指針完成的。我不確定你已經教過什麼，以及你應該弄清楚什麼。這是什麼水平的編程課？