【LC_Lesson7】---将两个有序链表合成新的一个有序链表

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

示例：

输入：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++实现：

 class Solution {

 public:

     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

         if(l1 == NULL)

             return l2;

         if(l2 == NULL)

             return l1;

         ListNode *p = l1;

         ListNode *q = l2;

         ListNode *result = new ListNode();

         ListNode *r = result;

         while(q && p)

         {

             if (q->val < p->val)

             {

                 r->next = q;

                 r = r->next;

                 q = q->next;

             }

             else

             {

                 r->next = p;

                 r = r->next;

                 p = p->next;

             }

         }

         if (q)

             r->next = q;

         if (p)

             r->next = p;

         return result->next;

     }

 };

思路二：

　　其次可以使用递归的方法，

巴特西

【LC_Lesson7】---将两个有序链表合成新的一个有序链表

最新文章

热门文章