题目链接

21. 合并两个有序链表

题目描述

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

示例：

  1. 输入：1->2->4, 1->3->4
  2. 输出：1->1->2->3->4->4

解题思路

1. 迭代

利用一个虚拟节点 dummyNode，遍历两个链表进行比较，哪个节点值小，dummyNode 就连接到哪个节点。

  1. public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  2.     ListNode dummyNode = new ListNode();
  3.     ListNode tmp = dummyNode;
  4.     while (list1 != null && list2 != null) {
  5.         if (list1.val <= list2.val) {
  6.             tmp.next = list1;
  7.             list1 = list1.next;
  8.         } else {
  9.             tmp.next = list2;
  10.             list2 = list2.next;
  11.         }
  12.         tmp = tmp.next;
  13.     }
  14.     tmp.next = list1 != null ? list1 : list2;
  15.     return dummyNode.next;
  16. }
  • 时间复杂度：LeetCode21. 合并两个有序链表 - 图1，其中 m 和 n 分别为两个链表的长度。

  • 空间复杂度：LeetCode21. 合并两个有序链表 - 图2

    2. 递归

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  if (list1 == null) {
      return list2;
  }
  if (list2 == null) {
      return list1;
  }
  if (list1.val <= list2.val) {
      list1.next = mergeTwoLists(list1.next, list2);
      return list1;
  } else {
      list2.next = mergeTwoLists(list1, list2.next);
      return list2;
  }
}

  • 时间复杂度：LeetCode21. 合并两个有序链表 - 图3，其中 m 和 n 分别为两个链表的长度。

  • 空间复杂度：LeetCode21. 合并两个有序链表 - 图4，其中 m 和 n 分别为两个链表的长度。递归调用需要的的栈空间大小取决于递归调用的深度。递归函数最多调用 M + N 次。