牛客网高频算法题系列-BM4-合并两个排序的链表

题目描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

  • 数据范围： 0 <= n <= 1000，-1000 <= 节点值 <= 1000
  • 要求：空间复杂度 O(1)，时间复杂度 O(n)

原题目见：BM4 合并两个排序的链表

解法一：链表遍历

  • 首先，判断特殊情况，如果链表一为空，直接返回链表二；如果链表二为空，直接返回链表一。
  • 否则，先声明一个新的假头结点，然后遍历链表一和链表二，过程如下：
    • 如果链表一为空，直接将链表二剩下的结点接到后面，并终止遍历
    • 如果链表二为空，直接将链表一剩下的结点接到后面，并终止遍历
    • 否则，比较链表一和链表二当前结点的大小，来判断下一个结点，然后处理下一个结点
  • 最后，返回合并后的链表。

代码

  1. public class Bm004 {
  2.     /**
  3.      * 合并两个排序的链表
  4.      *
  5.      * @param list1 链表一
  6.      * @param list2 链表二
  7.      * @return
  8.      */
  9.     public static ListNode merge(ListNode list1, ListNode list2) {
  10.         // 如果链表一为空，直接返回链表二
  11.         if (list1 == null) {
  12.             return list2;
  13.         }
  14.         // 如果链表二为空，直接返回链表一
  15.         if (list2 == null) {
  16.             return list1;
  17.         }
  18.         // 声明一个新的假头结点
  19.         ListNode newList = new ListNode(-1), next = newList;
  20.         // 遍历链表一和链表二
  21.         while (list1 != null || list2 != null) {
  22.             if (list1 == null) {
  23.                 // 如果链表一为空，直接将链表二剩下的结点接到后面，并终止遍历
  24.                 next.next = list2;
  25.                 break;
  26.             } else if (list2 == null) {
  27.                 // 如果链表二为空，直接将链表一剩下的结点接到后面，并终止遍历
  28.                 next.next = list1;
  29.                 break;
  30.             } else if (list1.val < list2.val) {  // 否则，比较链表一和链表二当前结点的大小，来判断下一个结点，然后处理下一个结点
  31.                 next.next = list1;
  32.                 list1 = list1.next;
  33.             } else {
  34.                 next.next = list2;
  35.                 list2 = list2.next;
  36.             }
  37.             next = next.next;
  38.         }
  39.         // 最后，返回合并后的链表
  40.         return newList.next;
  41.     }
  43.     public static void main(String[] args) {
  44.         // 1 -> 3 -> 5
  45.         ListNode list1 = ListNode.testCase3();
  46.         System.out.println("链表一");
  47.         ListNode.print(list1);
  48.         // 2 -> 4 -> 6
  49.         ListNode list2 = ListNode.testCase4();
  50.         System.out.println("链表二");
  51.         ListNode.print(list2);
  53.         ListNode newList = merge(list1, list2);
  54.         System.out.println("合并后的链表");
  55.         ListNode.print(newList);
  56.     }
  57. }

牛客网高频算法题系列-BM4-合并两个排序的链表 - 图1
牛客网高频算法题系列-BM4-合并两个排序的链表 - 图2
相信坚持的力量！