剑指Offer:面试题17——合并两个排序的链表

题目描述

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

思路1:

分别用p1,p2两个指针扫描两个有序链表,p3指针去构建新链表h3.

p1.val <= p2.val,则p3把p1指向的结点加入h3,p1后移动。反之,对p2进行对应操作。

代码:(未验证正确性,提交时显示超时,所以不知道功能是否实现,还是仅仅时间复杂度高?)

public ListNode Merge(ListNode list1,ListNode list2) {

        if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
} ListNode p1 = list1;
ListNode p2 = list2; ListNode list3;
if(list1.val <= list2.val){
list3 = list1;
}else{
list3 = list2;
}
ListNode p3 = list3; while(p1 != null && p2 != null){ if(p1.val <= p2.val){
p3.next = p1;
p1 = p1.next; }else{
p3.next = p2;
p2 = p2.next;
} p3 = p3.next;
} if(p1 == null){
p3.next = p2;
} if(p2 == null){
p3.next = p1;
} return list3;
}

思路2:

采用递归的思想

代码:

public ListNode Merge(ListNode list1,ListNode list2) {

        if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
} ListNode list3;
if(list1.val <= list2.val){
list3 = list1;
list3.next = Merge(list1.next, list2);
}else{
list3 = list2;
list3.next = Merge(list1, list2.next);
} return list3;
}
上一篇:基于Kubernetes构建企业容器云


下一篇:Maven学习笔记(二) :Maven的安装与配置