【LeetCode】剑指 Offer 25. 合并两个排序的链表 p145 -- Java Version

题目链接：https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

1. 题目介绍（25. 合并两个排序的链表）

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

【测试用例】：
示例1：

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

【条件约束】：

限制：

• 0 <= 链表长度 <= 1000

【相关题目】：

注意： 本题与主站 21. 合并两个有序链表 题目相同。

2. 题解

2.1 递归（原书题解）-- O(n+m)

时间复杂度O(n+m)，空间复杂度O(n+m)

就代码简单度来说，还是递归要比循环简单一些，但也要付出一些空间代价。

思想：
递归解法的思想还是十分简单的，首先主要就是对空链表的判断：

• 当链表1为空时，那么合并链表为链表2
• 当链表2为空时，那么合并链表为链表1
• 当链表1和2都为空时，那么合并链表也为空

判空完毕后，开始比较头节点：

• 当链表1头节点小于链表2头节点时，合并头节点为l1，递归寻找下一节点
• 当链表1头节点大于链表2头节点时，合并头节点为l2，递归寻找下一节点

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {// 判空if (l1 == null) return l2;else if (l2 == null) return l1;// 定义合并链表头节点ListNode mergeHead = null;// 合并过程// 1. 头节点比较，小的为当前节点// 2. 下一节点进入递归if (l1.val < l2.val){mergeHead = l1;mergeHead.next = mergeTwoLists(l1.next,l2);}else { mergeHead = l2;mergeHead.next = mergeTwoLists(l1,l2.next);}return mergeHead;}
}

2.2 循环 – O(n+m)

时间复杂度O(n+m)，空间复杂度O(1)

引入伪头节点： 由于初始状态合并链表中无节点，因此循环第一轮时无法将节点添加到合并链表中。解决方案：初始化一个辅助节点 n1 作为合并链表的伪头节点，将各节点添加至 n1 之后，n2 为 cur （当前节点）。

/*** 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) return list2;else if (list2 == null) return list1;ListNode n1 = new ListNode(0);ListNode n2 = n1;while (list1 != null && list2 != null){if (list1.val < list2.val){n2.next = list1;list1 = list1.next;}else{n2.next = list2;list2 = list2.next;}n2 = n2.next;}n2.next = list1 != null ? list1 : list2;return n1.next;}
}

3. 参考资料

[1] 面试题25. 合并两个排序的链表（伪头节点，清晰图解）-- 2.2图片来源