标签：链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路
两种解法：递归和非递归
递归：注意递归终止条件，还有递归方向，其实很好想，不要钻牛角尖非递归解法第一个是我自己写的，很冗余，第二个是别人精简的代码，忘借鉴我一开始的思路是，分list1 < list2和list1 >= list2,但又考虑到可能list1一直小，就加个内层循环，然后越来越复杂其实就两种点：判断大小，要不1<2,要不2<=1,一轮下来，指针往后走就行了，然后定义一个新头结点和当前节点（cur永远在比较大小的两个节点前，非空）。
拓展
LeetCode 23：合并k个排序链表，牛客地址
参考代码
递归解法
public ListNode Merge(ListNode list1, ListNode list2) {
if(list1 == null)
return list2;
if(list2 == null)
return list1;
if(list1.val < list2.val) {
list1.next = Merge(list1.next, list2);
return list1;
}else {
list2.next = Merge(list1, list2.next);
return list2;
}
}
别人优秀的非递归代码
//非递归
public ListNode Merge2(ListNode list1, ListNode list2) {
if(list1 == null)
return list2;
if(list2 == null)
return list1;
//定义两个指针
ListNode mergeHead = null;
ListNode current = null;
while(list1!=null && list2!=null) {
if(list1.val < list2.val) {
if(mergeHead == null) {
mergeHead = current = list1;
}else {
//current永远是当前节点，不为空
current.next = list1;
current = current.next;
}
//为什么要放在外面，循环要终止
list1 = list1.next;
}else {
if(mergeHead == null) {
mergeHead = current = list2;
}else {
current.next = list2;
current = current.next;
}
list2 = list2.next;
}
}
if(list1 == null)
current.next = list2;
if(list2 == null)
current.next = list1;
return mergeHead;
}
非递归，自己第一次写的
public ListNode Merge3(ListNode list1,ListNode list2) {
if( list1 == null)
return list2;
if(list2 == null)
return list1;
ListNode head = list1.val <= list2.val ? list1 :list2;
ListNode last = null;
while(list1 != null && list2 != null){
//System.out.println(list1.val);
while(list1!=null && list1.val <= list2.val){
if(list1.next!=null && list1.next.val >= list2.val){
ListNode temp = list1.next;
list1.next = list2;
list1 = temp;
}else{
if(list1.next == null)
last = list1;
list1 = list1.next;
}
}
while(list2!=null && list1!=null && list2.val < list1.val){
//System.out.println(list2.val);
if(list2.next!=null && list2.next.val >= list1.val){
ListNode temp = list2.next;
list2.next = list1;
list2 = temp;
}else{
if(list2.next == null)
last = list2;
list2 = list2.next;
}
}
}
if(list1 != null)
last.next = list1;
if(list2 != null)
last.next = list2;
return head;
}
自己第二次写的
//非递归
public ListNode Merge4(ListNode list1, ListNode list2) {
if(list1 == null)
return list2;
if(list2 == null)
return list1;
//定义新的头结点和当前节点
ListNode mergeHead = null;
if(list1.val <= list2.val){
mergeHead = list1;
list1 = list1.next;
}else{
mergeHead = list2;
list2 = list2.next;
}
//当前节点，永远在比较的两个节点前，非空
ListNode current = mergeHead;
while(list1!=null && list2!=null) {
if(list1.val < list2.val) {
current.next = list1;
list1 = list1.next;
}else{
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
if(list1 == null)
current.next = list2;
if(list2 == null)
current.next = list1;
return mergeHead;
}
还能再改进
public ListNode Merge5(ListNode list1, ListNode list2) {
if(list1 == null)
return list2;
if(list2 == null)
return list1;
//定义新的空头节点和当前节点
ListNode mergeHead = new ListNode(0);
ListNode current = mergeHead;
while(list1!=null && list2!=null) {
if(list1.val < list2.val) {
current.next = list1;
list1 = list1.next;
}else{
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
if(list1 == null)
current.next = list2;
if(list2 == null)
current.next = list1;
return mergeHead.next;
}
