剑指offer 16.代码的鲁棒性合并两个排序的链表

题目描述

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

本渣渣思路：分别遍历两个链表，将两个链表加入到arraylist中，再将arraylist转换成数组，用快排进行排序，之后将排序后的数组转换成链表即可

import java.util.ArrayList;
import java.util.List;

public class Merge {

//快排的方法
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基准位
temp = arr[low];

while (i<j) {
//先看右边，依次往左递减
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边，依次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}

}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}

//数组转换成链表
public ListNode arrayToListNode(int[] s) {
ListNode root = new ListNode(s[0]);//生成链表的根节点，并将数组的第一个元素的值赋给链表的根节点
ListNode other = root;//生成另一个节点，并让other指向root节点，other在此作为一个临时变量，相当于指针
for (int i = 1; i < s.length; i++) {//由于已给root赋值，所以i从1开始
ListNode temp = new ListNode(s[i]);//每循环一次生成一个新的节点,并给当前节点赋值
other.next = temp;//将other的下一个节点指向生成的新的节点
other = temp;//将other指向最后一个节点(other的下一个节点) other=other.getNext();
}
return root;
}

//方法主体

public ListNode Merge(ListNode list1,ListNode list2) {
if (list1==null&&list2==null) {
return null;
}
List<Integer> list=new ArrayList<Integer>();
while (list1!=null) {
list.add(list1.val);
list1=list1.next;
}
while (list2!=null) {
list.add(list2.val);
list2=list2.next;
}
int[] array=new int[list.size()];
for (int i = 0; i < list.size(); i++) {
array[i]=list.get(i);
}

quickSort(array, 0, array.length-1);
ListNode listNode=arrayToListNode(array);
return listNode;

}

class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}
}

大神思路

代码如下：

public ListNode Merge(ListNode list1, ListNode list2) {

if(list1==null)

return list2;

if(list2==null)

return list1;

ListNode res = null;

if(list1.val<list2.val){

res = list1;

res.next = Merge(list1.next, list2);

}else{

res = list2;

res.next = Merge(list1, list2.next);

}

return res;

}

更神仙的代码

递归版本：

 



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;
       }        
   }

非递归版本：

 



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.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;
        }else{
            current.next = list1;
        }
        return mergeHead;

剑指offer 16.代码的鲁棒性 合并两个排序的链表

题目描述

剑指offer 16.代码的鲁棒性合并两个排序的链表