网站开发有什么,内江市网站建设培训,西安快速排名,平度好的建设网站题目链接#xff1a;https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
1. 题目介绍#xff08;25. 合并两个排序的链表#xff09; 输入两个递增排序的链表#xff0c;合并这两个链表并使新链表中的节点仍然是递增排序的。 【测试用例】#xf…题目链接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(nm)
时间复杂度O(nm)空间复杂度O(nm)
就代码简单度来说还是递归要比循环简单一些但也要付出一些空间代价。 思想 递归解法的思想还是十分简单的首先主要就是对空链表的判断 当链表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(nm)
时间复杂度O(nm)空间复杂度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图片来源
