两个有序链表序列的合并（java实现）_java 合并两个有序链表

02-线性结构1 两个有序链表序列的合并（15 分）

List Merge( List L1, List L2 );

输入样例：

3
1 3 5
5
2 4 6 8 10

输出样例：

1 2 3 4 5 6 8 10 
NULL
NULL

思路：

1、两个链表，比较元素大小之后指针后移，最后把某个链表剩余的元素添加进来。

2、就不输出null null了。

 
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LinkedList<Integer> L1 = new LinkedList<>();
		LinkedList<Integer> L2 = new LinkedList<>();
		Scanner in = new Scanner(System.in);
		int n1 = in.nextInt();
		for(int i = 0 ;i<n1;i++) {
			L1.add(in.nextInt());
		}
		int n2 = in.nextInt();
		for(int i = 0 ;i<n2;i++) {
			L2.add(in.nextInt());
		}
		
		LinkedList<Integer> Lt = merge( L1,  L2);
		System.out.println(Lt);
	}
 
	public static LinkedList<Integer> merge(LinkedList<Integer> L1,LinkedList<Integer> L2) {
		Iterator<Integer> it1 = L1.iterator();
		Iterator<Integer> it2 = L2.iterator();
		LinkedList<Integer> L3 = new LinkedList<>();
		
		int n1 = L1.size();
		int n2 = L2.size();
		
//		System.out.println(n1+"  "+n2);
		
		Integer m1=0,m2=0;
		if(it1.hasNext())
			m1 = it1.next();
		if(it2.hasNext())
			m2 = it2.next();
		
		for(int i = 1,j = 1 ; i<=n1&&j<=n2 ; ) {
			
			switch(compare(m1,m2)) {
			case 1 : {
				L3.add(m2);
				j++;
				if(it2.hasNext())
					m2=it2.next();
			};
			break;
			
			case -1: {
				L3.add(m1);
				i++;
				if(it1.hasNext())
					m1=it1.next();
			};
			
			break;
			
			case 0 :{
				L3.add(m1);
				L3.add(m2);
				i++;
				j++;
				if(it1.hasNext())
					m1=it1.next();
				if(it2.hasNext())
					m2=it2.next();
			};
			break;
			default: break;
		}
		
		
	}
		if(it1.hasNext())
		{
			L3.add(m1);
			while(it1.hasNext())
			{
				
				L3.add(it1.next());
			}
		}
		else
		{
			L3.add(m2);
			while(it2.hasNext())
			{
			
				L3.add(it2.next());
			}
		}	 
		return L3;
}
 
	private static int compare(Integer m1, Integer m2) {
		// TODO Auto-generated method stub
		if(m1>m2)
			return 1;
		else if(m1==m2)
			return 0;
		else 
			return -1;
	
	}
}