题解 | #反转链表#
合并两个排序的链表
http://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
// 只要用指针从头开始,动态地比较两个链表中下一个元素的大小即可,空间和时间复杂度为O(n)
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
// 任何一个链表为空,返回结果都为另一个链表
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
// 先比较两个设置头结点
ListNode head = null;
if(list1.val < list2.val){
head = list1;
list1 = list1.next;
}
else {
head = list2;
list2 = list2.next;
}
// 动态扩充链表
ListNode first = head;
while(list1 != null && list2 != null){
// System.out.print(head.val);
if(list1.val < list2.val){
head.next = list1;
list1 = list1.next;
}
else {
head.next = list2;
list2 = list2.next;
}
head = head.next;
}
if(list1==null){
head.next = list2;
}
if(list2==null){
head.next = list1;
}
return first;
}
}