关于合并有序数组/链表的总结

 （尊重劳动成果，转载请注明出处：http://blog.csdn.net/qq_25827845/article/details/53872766冷血之心的博客）

 通过最近的研究，发现好多公司在笔试和面试中还是挺喜欢让你写一些合并类的程序。主要有合并两个有序数组和合并两个有序单链表（可扩展考虑如何合并K个有序链表），本博客中，对合并有序数组和合并有序链表做了一个总结，以便自己接下来的翻阅，也为了给小伙伴分享。

1、合并两个有序的数组

算法步骤如下：

• 建立一个可以容纳两个有序数组的新数组
• 通过对数组1和数组2中每位进行比较，存入新数组中
• 当某一个数组较短，比较结束后，将较长数组中剩余的元素都加入新数组中

代码如下：

package cn.ywq.test;

public class Client {

	public static void main(String[] args) {

		int[] a = { 1, 3, 5, 7, 12, 14, 23, 45, 46, 67, 89, 100 };
		int[] b = { 2, 4, 6, 8, 9, 68 };
		int[] result = Merge(a, b);
		for (int i : result) {
			System.out.println(i);
		}

	}

	private static int[] Merge(int a[], int b[]) {

		int result[] = new int[a.length + b.length];
		int i = 0, j = 0, k = 0; // i:用于标示a数组 j：用来标示b数组 k：用来标示传入的数组

		while (i < a.length && j < b.length) {
			if (a[i] <= b[j]) {
				result[k++] = a[i++]; // 这种用法  很厉害
			} else {
				result[k++] = b[j++]; // 这种用法  很厉害
			}
		}

		// 下边的两个循环是将长的数组剩下的部分存入result数组中
		while (i < a.length)
			result[k++] = a[i++];
		while (j < b.length)
			result[k++] = b[j++];

		return result;
	}
}

2、合并两个有序的单链表

步骤如下：

• 建立链表的结构
• 创建两个有序的单链表
• 调用合并方法进行合并操作

在合并方法中，通过对链表data域的比较和指针的移动，使用递归的方法来完成合并操作。

代码如下：

package com.ywq.test2;

import org.junit.Test;

public class Solution2 {

	@Test
	public void test() {
		//创建有序链表list1  0-2-5-7-9
		ListNode list1 = new ListNode(0);  
		list1.next = new ListNode(2);  
		list1.next.next = new ListNode(5);  
		list1.next.next.next = new ListNode(7); 
		list1.next.next.next.next = new ListNode(9);
	 
		//创建有序链表list2  1-3-6-8
        ListNode list2 = new ListNode(1);  
        list2.next = new ListNode(3);  
        list2.next.next = new ListNode(6);  
        list2.next.next.next = new ListNode(8); 
  
        //调用合并方法
        ListNode list3 = mergeKLists(list1, list2); 
        //将结果输出
        while (list3 != null) {  
            System.out.println(list3.val);  
            list3 = list3.next;  
        }  
	}

	public ListNode mergeKLists(ListNode list1, ListNode list2) {
		
		ListNode result=null;
		
		if (list1 == null && list2 == null) {  
            return null;  
        }  
        if (list1 == null) {  
            result = list2;  
            return result;  
        }  
        if (list2 == null) {  
            result = list1;  
            return result;  
        }  
        if (list1.val > list2.val) {  
            result = list2;  
            list2 = list2.next;  
        } else {  
            result = list1;  
            list1 = list1.next;  
        }  
        result.next = mergeKLists(list1, list2);  
        
        return result;  
		
	     
	
	}
	
}


class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

 如果对你有帮助，记得点赞哦~欢迎大家关注我的博客，可以进群366533258一起交流学习哦~