链接列表的递归递增和递归降序功能

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（或零），在该情况下，递归函数只是返回列表，否则它会在递归函数中跟随代码合并返回的左列表和右列表，并返回合并列表。

您是否学过如何将链表分成两个列表？通常这是使用两个指针完成的。我不确定你已经教过什么，以及你应该弄清楚什么。这是什么水平的编程课？