21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

想法一：三指针法…

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(!l1||!l2) { return (!l1?l2:l1); } ListNode* p1 = l1, *p2 = l2, *temp = nullptr; int tag; while(p1&&p2) { if(p1->val>=p2->val) { if(temp == nullptr) { temp = p2; p2=p2->next; tag = 2; continue; } temp->next = p2; p2 = p2->next; temp = temp->next; } else { if(temp == nullptr) { temp = p1; p1=p1->next; tag = 1; continue; } temp->next = p1; p1 = p1->next; temp = temp->next; } } temp->next = (p1?p1:p2); return (tag==1?l1:l2); }};

想法二：递归

每一层都是比较小val的那个指向下一个比较大的，最后判断l1还是l2不是nullptr

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(!l1||!l2) return (l1?l1:l2); //递归返回 if(l1->val > l2->val) { l2->next = mergeTwoLists(l1,l2->next); return l2; } else { l1->next = mergeTwoLists(l1->next,l2); return l1; } } };