武力剑指的是提议25。合并两个排序的链表。
题目
指剑要约25。合并两个排序的链表。
思路1
事实上，合并和排序是将两个数字组合成一个有序的数组。
由于两个链表的元素已经是递增了(必要条件)，我们可以遍历两个链表，判断两个节点之间的大小关系，然后交替向前移动，合并成一个新的链表。
因为合并后需要返回一个新的链表，无法判断l1和l2链表的值，所以可以创建一个伪头节点，相当于标识这个链表，这样最终的结果就是伪头节点的dummy.next。
代码
解决方案类{
公共列表节点合并列表(列表节点l1，列表节点L2){ 0
//创建虚拟头节点
ListNode dummy=new ListNode(-1)；
ListNode temp=dummy
//是合并排序中两个数字组合成一个有序数组。
//确保两个链接列表都有效且不为空。
//如何确定合并的大小，请注意这里要重新创建节点。
while (l1！=null l2！=null){ 0
if(L1 . val L2 . val){ 0
temp . next=new ListNode(L1 . val)；
temp=temp.next
l1=l1.next
} else {
temp . next=new ListNode(L2 . val)；
temp=temp.next
l2=l2.next
}
}
//判断是否已经遍历了两个链表。
while (l1！=null){ 0
temp . next=new ListNode(L1 . val)；
temp=temp.next
l1=l1.next
}
while (l2！=null){ 0
temp . next=new ListNode(L2 . val)；
temp=temp.next
l2=l2.next
}
//答案是虚拟头节点的下一个节点。
返回dummy.next
}
}
复杂度分析
复杂度：\(O(M ^ N)\)，M和N分别是l1和l2链表的长度。
空间复杂度：\ O(1)\)
我走得很慢，但我从不后退！
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/103397.html