利用递归和非递归方法合并两个有序链表：
注意点： 1、代码中以输入的方式生成两个链表，在生成完毕第一个链表之后要将cin的内容清空。不然会引起第二个链表无法输入生成的问题。
#include<iostream> #include<vector> using namespace std; struct Node { int val; Node* next; Node(int num):val(num),next(nullptr){} }; Node* CreatList() { Node* head = new Node(0); Node* ptr = head; cout << "Please input a number(q to quit): "; int temp; while (cin >> temp) { Node* newNode = new Node(temp); newNode->next = ptr->next; ptr->next = newNode; ptr = newNode; cout << "Please input a number(q to quit): "; } while (getchar() != '\n'); cin.clear(); return head->next; } Node* MerageList(Node* list1, Node* list2) { if (list1 == nullptr || list2 == nullptr) return list1 == nullptr ? list2 : list1; Node* head = new Node(0), *ptr = head; while (list1 != nullptr&&list2 != nullptr) { if (list1->val < list2->val) { ptr->next = list1; list1 = list1->next; ptr = ptr->next; } else { ptr->next = list2; list2 = list2->next; ptr = ptr->next; } } if (list1 == nullptr) ptr->next = list2; else ptr->next = list1; ptr = head->next; delete head; return ptr; } Node* MerageListRe(Node* list1, Node* list2) { Node* head = nullptr; if (list1 == nullptr || list2 == nullptr) return list1 == nullptr ? list2 : list1; if (list1->val < list2->val) { head = list1; head->next = MerageListRe(list1->next, list2); } else { head = list2; head->next = MerageListRe(list1, list2->next); } return head; } void Show(Node* list) { while (list) { cout << list->val << " "; list = list->next; } cout << endl; } int main() { Node* head1 = CreatList(); Show(head1); Node* head2 = CreatList(); Show(head2); //Node* merageList = MerageList(head1, head2); //Show(merageList); Node* merageListRe = MerageListRe(head1, head2); Show(merageListRe); return 0; }