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

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) {

 更神仙的代码

递归版本：