合并两个有序数组/链表

• 合并两个数组
  比如数组：

int[] a ={1,3,6,9,13,45,99};
int[] b= {2,4,6,8,9,33,55,77};

合并后：

1 2 3 4 6 6 8 9 9 13 33 45 55 77 99

算法：
提供一个新数组，将原数组中较小的值放进去

 /**
     * 将已排序好的两个数组合并
     * 时间复杂度 o(n) 空间复杂度o(n)
     * @param a
     * @param b
     * @return
     */
    public static int[] arraySort(int[] a,int[] b){
        int a_length=a.length;
        int b_length=b.length;
        int result[]=new int[a_length+b_length];
        int i=0,j=0,k=0;
        while (i<a_length && j<b_length){
            if (a[i]<b[j]){
                result[k++]=a[i++];
            }else {
                result[k++]=b[j++];
            }
        }

        while (i<a_length){
            result[k++]=a[i++];
        }
        while (j<b_length){
            result[k++]=a[j++];
        }

//        if (i==a_length){
//            System.arraycopy(b,j,result,k,b.length-j);
//        }
//        if (j==b_length){
//            System.arraycopy(a,i,result,k,a.length-i);
//        }
        return result;
    }

---

• 链表
  可不使用另外的内存空间
  循环：

 /**
     * 尾插法
     * @param a
     * @param b
     * @return
     */
    public static Node sort_node_loop(Node a,Node b){
        if (null==a){
            return b;
        }
        if (null==b){
            return a;
        }

        //初始化，找到头结点
        Node tmpa=null,tmpb=null,head=null;

        if (a.value<=b.value){
            head=a;
            tmpa=a.next;
            tmpb=b;
        }else {
            head=b;
            tmpa=a;
            tmpb=b.next;
        }

        //尾插法：
        Node tmp=head;
        while (null!=tmpa && null!=tmpb){
            if (tmpa.value<=tmpb.value){
                tmp.next=tmpa;
                tmp=tmpa;
                tmpa=tmpa.next;
            }else {
                tmp.next=tmpb;
                tmp=tmpb;
                tmpb=tmpb.next;
            }
        }
        tmp.next=null==tmpa?tmpb:tmpa;

        return head;

    }

递归

 /**
     * 递归法  尾插
     * @param a
     * @param b
     * @return
     */
    public static Node sort_node_recursive(Node a,Node b){
        if (null==a){
            return b;
        }
        if (null==b){
            return a;
        }

        Node head=null;
        if (a.value<=b.value){
            head=a;
            head.next=sort_node_recursive(a.next,b);
        }else {
            head=b;
            head.next=sort_node_recursive(a,b.next);
        }
        return head;

    }

另附 新建一个node链表

    /**
     * 生成一个单链表
     * @param a
     * @return
     */
    public static Node generate(int[] a){
        if(null==a || a.length==0)return null;
        //初始化
        Node head,tmp;
        head=new Node();
        head.value=a[0];
        tmp=head;

        //
        int i=1;
        while (i<a.length){
            Node node=new Node();
            node.value=a[i];
            tmp.next=node;
            tmp=tmp.next;
            i++;
        }
        return head;
    }