将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
太久没复习数据结构和C/C++的链表实现了，一时间感觉无从下手头蒙了半天，花了半天时间整理了下单链表的基本知识，同时整理了下单链表的前序插入和后续插入。如下链接
https://www.cnblogs.com/szhb-5251/p/11770322.html
一. 解题思路
思路一：
1) 两个链表均是有序的，而且各个节点也都是实际存在的，可以考虑重新拉一个链表出来，然后依次扫描两个有序链表，有序的将元素分别插入在新链表上面。一直到某条链表扫描结束，然后把另外一条链表剩余的元素插入在当前新链表的后面即可。
C++实现：
1 class Solution { 2 public: 3 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { 4 if(l1 == NULL) 5 return l2; 6 if(l2 == NULL) 7 return l1; 8 ListNode *p = l1; 9 ListNode *q = l2; 10 ListNode *result = new ListNode(0); 11 ListNode *r = result; 12 13 while(q && p) 14 { 15 if (q->val < p->val) 16 { 17 r->next = q; 18 r = r->next; 19 q = q->next; 20 } 21 else 22 { 23 r->next = p; 24 r = r->next; 25 p = p->next; 26 } 27 } 28 if (q) 29 r->next = q; 30 if (p) 31 r->next = p; 32 return result->next; 33 } 34 };
思路二：
其次可以使用递归的方法，
原文链接: https://www.cnblogs.com/szhb-5251/p/11773200.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/305233
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
