21. 合并两个有序链表

难度: 简单

来源: 每日一题 2023.08.06

---

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

示例 1：

输入：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 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

    }
}

分析与题解

---

• 双指针

  这个题目我都快做吐了, 直接就是双指针法, 我们需要通过两个指针在两个链表中进行移动, 如果两个链表当前节点都不为 null, 进入循环判断.

  // 双指针法
  ListNode headNode = null, nowNode = null;
  while(list1 != null && list2 != null) {
      if (list1.val < list2.val) {
          if (nowNode == null) {
              nowNode = list1;
              headNode = nowNode;
          } else {
              nowNode.next = list1;
              nowNode = nowNode.next;
          }
          list1 = list1.next;
  
      } else {
          if (nowNode == null) {
              nowNode = list2;
              headNode = nowNode;
          } else {
              nowNode.next = list2;
              nowNode = nowNode.next;
          }
          list2 = list2.next;
      }
  }
  

  如果有任意一个链表遍历完成直接退出循环, 并把另外一个链表添加到尾部即可. 这样可以大大提升运行效率.

  if (list1 != null) { 
      if (nowNode == null) {
          nowNode = list1;
          headNode = nowNode;
      } else {
          nowNode.next = list1;
          nowNode = nowNode.next;
      }
  }
  if (list2 != null) { 
      if (nowNode == null) {
          nowNode = list2;
          headNode = nowNode;
      } else {
          nowNode.next = list2;
          nowNode = nowNode.next;
      }
  }
  

  整体逻辑代码如下所示.

  /**
  * Definition for singly-linked list.
  * public class ListNode {
  *     int val;
  *     ListNode next;
  *     ListNode() {}
  *     ListNode(int val) { this.val = val; }
  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  * }
  */
  class Solution {
      public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          if (list1 == null && list2 == null) {
              return null;
          }
          // 双指针法
          ListNode headNode = null, nowNode = null;
          while(list1 != null && list2 != null) {
              if (list1.val < list2.val) {
                  if (nowNode == null) {
                      nowNode = list1;
                      headNode = nowNode;
                  } else {
                      nowNode.next = list1;
                      nowNode = nowNode.next;
                  }
                  list1 = list1.next;
  
              } else {
                  if (nowNode == null) {
                      nowNode = list2;
                      headNode = nowNode;
                  } else {
                      nowNode.next = list2;
                      nowNode = nowNode.next;
                  }
                  list2 = list2.next;
              }
          }
          if (list1 != null) { 
              if (nowNode == null) {
                  nowNode = list1;
                  headNode = nowNode;
              } else {
                  nowNode.next = list1;
                  nowNode = nowNode.next;
              }
          }
          if (list2 != null) { 
              if (nowNode == null) {
                  nowNode = list2;
                  headNode = nowNode;
              } else {
                  nowNode.next = list2;
                  nowNode = nowNode.next;
              }
          }
          return headNode;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(Min(m , n)), 一次遍历循环, 时间复杂度与较短的链表长度相关.
  • 空间复杂度: O(1), 常量级别的空间复杂度.

  结果如下所示.