题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
时间限制：1秒 空间限制：32768K
本题知识点：链表
代码实现
/*
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 result = null;
ListNode current = null;
while(list1!=null && list2!=null){
if(list1.val <= list2.val){
if(result == null){
result = list1;
current = result;
}else{
current.next = list1;
current = list1;
}
list1 = list1.next;
}else{
if(result == null){
result = list2;
current = result;
}else{
current.next = list2;
current = list2;
}
list2 = list2.next;
}
}
if(list1 == null){
current.next = list2;
}else{
current.next = list1;
}
return result;
}
}
解题思路
这道题还是考察的我们对链表知识的掌握，还没掌握的同学请看我前面几道题，或者去数据结构和算法系列的链表的文章。
首先，我们进行是否为空的判断，如果为空我们就直接返回另一个链表即可。
然后我们定义合并后的链表的头结点 result 和当前结点 current。当我们进行合并选取下一个结点的时候分为两种情况。第一种是链表1当前结点和链表2当前结点都不为空，然后我们选择相对较小的那个加入合并后的链表，然后把被选择的链表当前结点更新为下一个结点，然后依次循环判断；第二种情况是其中一个链表当前结点为空了，那么我们直接把另外一个链表剩余的结点合并到结果链表即可。
代码中 result 空判断，是因为 result 和 current 结点还都为空，所以直接把选择的结点赋值给 result 和 current，如果不为空，那么就把 current 的指针指向被选择结点。
