力扣HOT100之链表：21. 合并两个有序链表

这道题我用比较简单的思路来做的，直接定义一个新的链表，然后不断遍历两个链表，将较小的值填到链表中，被填入到新的链表后，对应的指针后移一位。当一条链表遍历结束而另一条链表没有遍历结束时，直接将新链表的后继节点指向没有遍历结束的节点。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* virtual_head = new ListNode();ListNode* temp = virtual_head;while(list1 && list2){   //当list1和list2都没有遍历结束if(list1 -> val < list2 -> val){temp -> next = new ListNode(list1 -> val);list1 = list1 -> next;}else{temp -> next = new ListNode(list2 -> val);list2 = list2 -> next;} temp = temp -> next;}if(!list1 && list2)  //list2没遍历完temp -> next = list2;if(!list2 && list1)  //list1没遍历完temp -> next = list1;return virtual_head -> next;}
};

AC完了以后看了下灵神的题解，他写了两种解法，一种是迭代法（就是我的思路），另一种是递归法，递归的代码还挺简洁的，下面说一下递归的主要思想。
递归法就是不断遍历两个链表，存储值较小的节点作为头节点返回，而头节点的后继节点则由mergeTwoLists函数返回，当其中一条链表遍历到末端时，则直接将另一条链表的当前节点作为后继节点返回。

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {//处理终止条件if(!list1) return list2;if(!list2) return list1;//递归主体逻辑if(list1 -> val < list2 -> val){list1 -> next = mergeTwoLists(list1 -> next, list2);return list1;}else{list2 -> next = mergeTwoLists(list2 -> next, list1);return list2;}}
};