北京市地铁建设公司网站,推广普通话喜迎十二大手抄报,广州仿站定制模板建站,建设专业网站排名描述
输入两个递增的链表#xff0c;单个链表的长度为n#xff0c;合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围#xff1a; 0≤n≤1000#xff0c;−1000≤节点值≤1000
如输入{1,3,5},{2,4,6}时#xff0c;合并后的链表为{1,2,3,4,5,6}#xff0c;…描述
输入两个递增的链表单个链表的长度为n合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围 0≤n≤1000−1000≤节点值≤1000
如输入{1,3,5},{2,4,6}时合并后的链表为{1,2,3,4,5,6}所以对应的输出为{1,2,3,4,5,6}转换过程如下图所示 或输入{-1,2,4},{1,3,4}时合并后的链表为{-1,1,2,3,4,4}所以对应的输出为{-1,1,2,3,4,4}转换过程如下图所示 示例1
输入
{1,3,5},{2,4,6}
返回值
{1,2,3,4,5,6}示例2
输入
{},{}
返回值
{}示例3
输入
{-1,2,4},{1,3,4}
返回值
{-1,1,2,3,4,4}
思路分析
方法一
使用递归来进行求解
终止条件两链表其中一个为空时返回另一个链表当前递归内容若pHead1.val pHead2.val 将较小的pHead1.next与merge后的表头连接即pHead1.next Merge(pHead1.next,pHead2); pHead2.val较大时同理每次的返回值排序好的链表头
复杂度O(mn) O(mn)
代码
import java.util.*;public class Solution {/*** * param pHead1 ListNode类 * param pHead2 ListNode类 * return ListNode类*/public ListNode Merge (ListNode pHead1, ListNode pHead2) {if(pHead1null){return pHead2;}if(pHead2null){return pHead1;}if(pHead1.valpHead2.val){pHead2.nextMerge(pHead1,pHead2.next);return pHead2;}else{pHead1.nextMerge(pHead1.next,pHead2);return pHead1;}}
}
方法二
空间O(1)的思路 创建一个虚拟结点和一个哨兵结点 当pHead1与pHead2都不为null时循环 哪个的val小哪个赋给虚拟结点的next虚拟结点后移。 退出循环后哪个pHead不为空哪个结点包括剩下的给虚拟结点的next 最后返回哨兵结点的next
代码
import java.util.*;public class Solution {/*** * param pHead1 ListNode类 * param pHead2 ListNode类 * return ListNode类*/public ListNode Merge (ListNode pHead1, ListNode pHead2) {ListNode dummynew ListNode(-1);ListNode resdummy;while(pHead1!nullpHead2!null){if(pHead1.valpHead2.val){dummy.nextpHead2;pHead2pHead2.next;dummydummy.next;}else if(pHead1.valpHead2.val){dummy.nextpHead1;pHead1pHead1.next;dummydummy.next;}}if(pHead1!null){dummy.nextpHead1;}if(pHead2!null){dummy.nextpHead2;}return res.next;}
}
