signed

QiShunwang

“诚信为本、客户至上”

LeetCode题解——合并两个有序链表

2021/5/14 21:39:00   来源:

LeetCode题解——合并两个有序链表

  • 题目介绍

  • 解题思路
  1. 这题的解题思路可以分为两种,第一种暴力解法,直接创建一个新的链表,然后比较2个输入链表,将小的节点一次赋值过去,然后最后返回创建的新的链表
  2. 第二种解法,类似于动态规划的思想,我每次比较两个链表选出最小的节点,知道把所有节点连上
  3. 比如图中的例子,首先利用mergeTwoLists函数选出1,同时1的next节点指向mergeTwoLists(剩下的2个链表)选出的第二大节点,依次递归调用
  • 代码示例
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
         if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {//l1链表的头节点较小
            l1->next = mergeTwoLists(l1->next, l2);//l1的next指向下一次mergeTwoLists函数选出来的最小值
            return l1;//返回l1的头节点
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};