题解 | #合并两个排序的链表#
合并两个排序的链表
https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337
非递归插入法
将任意一个原始链表（list1）作为返回表，将另一个作为参数表
根据大小将节点插入最后返回list1即可
时间复杂度O（n），空间复杂度O（1）
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
ListNode next = null;
ListNode cur = list1;
while(list2 != null){
if(cur.val<= list2.val && cur.next != null && cur.next.val<= list2.val){
cur = cur.next;
}else if(cur.val<=list2.val){
next = list2.next;
list2.next = cur.next;
cur.next = list2;
cur = list2;
list2 = next;
}else {
next = list2.next;
list2.next = cur;
list1 = list2;
list2 = next;
}
}
return list1;
}
}
查看20道真题和解析