自适应网站建设需要注意什么网络营销的整体概念
题目链接: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图片来源