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

  1. 示例1：
  2. 输入: l1 = [1,2,4], l2 = [1,3,4]
  3. 输出: [1,1,2,3,4,4]
  5. 示例2:
  6. 输入:l1 = [], l2 = []
  7. 输出:[]
  9. 示例3:
  10. 输入:l1 = [], l2 = [0]
  11. 输出:[0]

迭代

  1. 建立一个哑节点 temp ，指向新链表的表头节点
  2. 遍历两个连博鳌，让当前节点 guard 指向较小的节点，并使得较小链表往后移一位
  3. 循环结束时，让 guard 指向非空的链表

  4. 返回 temp->next ：temp只是为了最终的返回做准备

    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     struct ListNode *next;
    6. * };
    7. */
    8. struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    9.  if (!l1) return l2;
    10.  if (!l2) return l1;
    11.  // temp是为了最后的返回初始化一个链表
    12.  struct ListNode *temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    13.  // 哨兵 作为尾节点持续不断的找当前两个链表头的比较小的节点
    14.  struct ListNode *guard = temp;
    15.  while (l1 && l2) {
    16.      if (l1->val < l2->val) {
    17.          guard->next = l1;
    18.          l1 = l1->next;
    19.      } else {
    20.          guard->next = l2;
    21.          l2 = l2->next;
    22.      }
    23.      guard = guard->next;
    24.  }
    25.  // 最后一定有一个多余的节点没被比较，找到它即可
    26.  guard->next = (l1==NULL)?l2:l1;
    27.  return temp->next;
    28. }

    递归

  5. l1 为空那么返回 l2 , l2 为空则返回 l1

  6. 比较 l1 和 l2 的头节点，找到最小的节点，然后大的节点和剩下的再做比较 ```c /**
    • Definition for singly-linked list.
    • struct ListNode {
    • int val;
    • struct ListNode *next;
    • }; */

struct ListNode mergeTwoLists(struct ListNode l1, struct ListNode* l2){ if (l1 == NULL) { return l2; } if (l2 == NULL) { return l1; } if (l1->val <= l2->val) { l1->next = mergeTwoLists(l1->next,l2); return l1; } else { l2->next = mergeTwoLists(l1,l2->next); return l2; } } ```