leetcode-合并两个有序链表

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 val) { // 如果新链表还未添加过节点，则设置新链表的头结点和尾结点都为l1 if (Newhead == NULL) { Newhead = Newtail = l1; } else { // 否则将尾结点的next指向l1，并更新尾结点为新添加的节点 Newtail->next = l1; Newtail = Newtail->next; } // 移动l1指针至下一个节点 l1 = l1->next; } else { // 类似地处理l2的情况 if (Newhead == NULL) { Newhead = Newtail = l2; } else { Newtail->next = l2; Newtail = Newtail->next; } l2 = l2->next; } } // 当某一个链表遍历完之后，将未遍历完的链表剩余部分连接到新链表的尾部 if (l1) { Newtail->next = l1; } if (l2) { Newtail->next = l2; } // 返回新链表的头结点 return Newhead; }

  方法二

  /**
   * 定义单链表结构体
   * 结构体中包含整数值val以及指向下一个节点的指针next
   */
  typedef struct ListNode ListNode;
  struct ListNode {
      int val;
      struct ListNode *next;
  };
  /**
   * 函数mergeTwoLists接收两个单链表（list1和list2）作为参数，
   * 合并这两个已排序的链表，并返回合并后的新链表，新链表中的元素仍按升序排列。
   *
   * 思路：
   * 1. 创建新的链表用于存放合并后的节点，初始化新链表头结点和尾结点。
   * 2. 使用while循环比较两个链表当前节点的值，将较小值的节点添加到新链表中。
   * 3. 当某个链表遍历完后，将另一个未遍历完链表的剩余部分添加到新链表尾部。
   * 4. 最后，释放初始分配给新链表头结点的空间，并返回新链表的第二个节点（实际内容的起始节点）。
   */
  struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
      // 判断输入链表是否为空
      if (list1 == NULL) {
          return list2;
      }
      if (list2 == NULL) {
          return list1;
      }
      // 创建临时指针保存原始链表，避免改变它们
      ListNode* l1 = list1;
      ListNode* l2 = list2;
      // 分配内存创建新链表的头结点和尾结点
      ListNode *Newhead, *Newtail;
      Newhead = Newtail = (ListNode*)malloc(sizeof(ListNode));
      // 注意：这里实际上创建了一个空节点作为占位符，其next指针将指向实际的第一个合并节点
      // 循环遍历两个链表，将较小值的节点依次添加到新链表中
      while (l1 && l2) {
          if (l1->val val) {
              Newtail->next = l1;
              Newtail = Newtail->next;
              l1 = l1->next;
          } else {
              Newtail->next = l2;
              Newtail = Newtail->next;
              l2 = l2->next;
          }
      }
      // 将剩余未遍历完的链表连接到新链表尾部
      if (l1) {
          Newtail->next = l1;
      }
      if (l2) {
          Newtail->next = l2;
      }
      // 获取新链表的实际头部（即第一个有效节点），释放占位头结点的空间
      ListNode* next = Newhead->next;
      free(Newhead);
      Newhead = NULL; // 可选，置空便于调试或后续操作
      // 返回合并后的新链表的实际头部节点
      return next;
  }