合并两个有序链表

大忽悠爱学习

发布于 2022-05-05 11:09:04

1.2K00

代码可运行

文章被收录于专栏：c++与qt学习c++与qt学习

运行总次数：0

代码可运行

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

示例 1：

c++代码： 思路1：开辟一个新链表用来存放新的合并后的升序链表，每一次从l1和l2链表分别取出来一个节点，判断两个节点的值哪一个大，大的节点跟在小的节点后面，小的节点尾插到新链表后面，并且还有判断l1和l2哪个链表长度更长，当出现一个链表遍历完后，另一个链表剩余部分就直接尾插到新链表后面

#include<iostream>
using namespace std;
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* l1, ListNode* l2) 
    {
        //整合的新链表没有头结点
        ListNode* newList = new ListNode();//该链表用来存放整合后的数据
        ListNode* end = newList;//指向当前链表尾节点
        ListNode* new2 = new ListNode(l1->val > l2->val ? l1->val : l2->val);//取较大的值
        ListNode* new1 = new ListNode(l2->val < l1->val ? l2->val : l1->val, new2);//那么取较小的值,并且直接指向较大值的节点
        newList->val = new1->val;
        end->next = new2;
        end = new2;
        l1 = l1->next;
        l2 = l2->next;
        while (l1 != NULL&& l2 != NULL)
        {
            //这边新链表插入数据使用尾插法
               new2 = new ListNode(l1->val>l2->val?l1->val:l2->val);//取较大的值
               new1 = new ListNode(l2->val<l1->val?l2->val:l1->val,new2);//那么取较小的值,并且直接指向较大值的节点
                end->next = new1;
                end = new2;
                l1 = l1->next;
                l2 = l2->next;
        }    
        //若l1链表比较短，那l2剩余节点直接尾插到新链表尾部，同理l2较短也是如此
        if (l1 == NULL)
        {
            while (l2 != NULL)
            {
                ListNode* newL2 = new ListNode(l2->val);
                end->next = newL2;
                end = newL2;
                l2 = l2->next;
            }
        }
        if (l2 == NULL)
        {
            while (l1 != NULL)
            {
                ListNode* newL1 = new ListNode(l1->val);
                end->next = newL1;
                end = newL1;
                l1 = l1->next;
            }
        }
        return newList;
    }
};
//测试-----------------
//为链表赋值---l链表没有头结点
void input(ListNode* l)
{
    //输入-1结束赋值
    int num = 0;
    cin >> num;
    if (num == -1)
        return;
    l->val = num;
    //尾插法
    ListNode* end = l;
    while (1)
    {
        cin >> num;
        if (num == -1)
            return;
        ListNode* newnode =new ListNode(num);
        end->next = newnode;
        end = newnode;
    }
}
//打印输出链表
void display(ListNode* l)
{
    if (l == NULL)
        return;
    cout << l->val;
    display(l->next);
}
void test()
{
    ListNode* l1 = new ListNode();
    ListNode* l2 = new ListNode();
    cout << "请为l1链表赋值：" << endl;
    input(l1);
    cout << "输出l1链表: " << endl;
    display(l1);
    cout << endl;
    cout << "请为l2链表赋值：" << endl;
    input(l2);
    cout << "输出l2链表: " << endl;
    display(l2);
    cout << endl;
    cout << "l1和l2链表结合后的结果为：" << endl;
    Solution s;
   ListNode* l3= s.mergeTwoLists(l1, l2);
   display(l3);
   cout << endl;
}
int main()
{
    test();
    system("pause");
    return 0;
}

递归写法

class Solution {
public:
     //递归写法
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        if (l1 == NULL)//如果l1链表先遍历完，那就返回当前l2链表
            return l2;
        if (l2 == NULL)
            return l1;
        if (l1->val <= l2->val)
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
};