题目链接:https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337
题目描述
输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围: 0≤n≤1000,-1000≤节点值≤1000
要求:空间复杂度 O(1),时间复杂度 O(n)
如输入{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}
解题代码
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
//记录新链表的头
ListNode newHead = null;
//记录新链表的尾
ListNode newTail = null;
//任一为空都跳出循环
while (list1 != null && list2 != null) {
//比较,找出比较小的节点
ListNode tmp = list1.val < list2.val ? list1 : list2;
//节点较小的链表向下走一步
if (tmp == list1) {
list1 = list1.next;
} else {
list2 = list2.next;
}
//第一次插入
if (newHead == null) {
newHead = tmp;
newTail = tmp;
} else {
//不是第一次插入
newTail.next = tmp;
newTail = newTail.next;
}
}
//任一链表为空,新链表连接不为空的链表
if (list1 == null) {
newTail.next = list2;
} else {
newTail.next = list1;
}
return newHead;
}
}
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名,转载请...
最后编辑时间为:
2022/07/14 15:32:58
如果你觉得文章对你有帮助,那就请作者喝杯咖啡吧☕
0
条评论
