题目

中文

https://leetcode-cn.com/problems/merge-two-sorted-lists/submissions/
image.png

英文

  1. Merge Two Sorted Lists
    https://leetcode.com/problems/merge-two-sorted-lists/submissions/
    Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
    Constraints:
  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both l1 and l2 are sorted in non-decreasing order.

Merge vt. 合并
splice v 拼接 splicing
non-decreasing 非递减的。

题解

第一次

我知道递归可以解决，
朴素暴力方法可以直接比较来一个一个接上。
太麻烦 看题解

  1. struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2)
  2. {
  3.     if (l1 == NULL)
  4.         return l2;
  5.     if (l2 == NULL)
  6.         return l1;
  7.     struct ListNode *mergeHead = NULL;
  8.     if (l1->val < l2->val)
  9.     {
  10.         mergeHead = l1;
  11.         mergeHead->next = mergeTwoLists(l1->next, l2);
  12.     }
  13.     else
  14.     {
  15.         mergeHead = l2;
  16.         mergeHead->next = mergeTwoLists(l1, l2->next);
  17.     }
  18.     return mergeHead;
  19. }

递归 解法
image.png
1 终止条件：其中一条链表为空 或者都为空 l1为空 应该return l2 将l2交上去 l2为空则交l1 return l1
两条都为空 实际上这里面也判断了
2 返回值 返回给上一层的 应该是当前对比的结果接着之前的 之后接要处理的。
3 本层递归任务 比较两个节点值大小 将小的放前面 之后再递归进行比较

遇到的问题

递归理解困难 其他还好