学步园

描述
两个线性单链表A和B中的元素（数据长度和元素由键盘输入），编写算法将A表和B表归并成一个按元素交替链接（a1、b1、a2、b2……）的表C，表长度大的把剩余元素接到C后面即可，并要求利用原表（即A和B表的）节点空间存储表C。
样例输入
6
2 4 5 7 8 9
3
3 2 1
样例输出
2 3 4 2 5 1 7 8 9
参考代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
		cin.readLine();
		String ds1[] = cin.readLine().split(" ");
		List<Character> list1 = new ArrayList<Character>();
		for(int i = 0;i < ds1.length;++ i){
			list1.add(ds1[i].charAt(0));
		}
		cin.readLine();
		String ds2[] = cin.readLine().split(" ");
		List<Character> list2 = new ArrayList<Character>();
		for(int i = 0;i < ds2.length;++ i){
			list2.add(ds2[i].charAt(0));
		}
		List<Character> list = new ArrayList<Character>();
		Iterator<Character>  it1 = list1.iterator();
		Iterator<Character>  it2 = list2.iterator();
		while(it1.hasNext() || it2.hasNext()){
			if(it1.hasNext()){
				list.add(it1.next());
			}
			if(it2.hasNext()){
				list.add(it2.next());
			}
		}
		Iterator<Character>  it = list.iterator();
		while(it.hasNext()){
			System.out.print(it.next()+" ");
		}
		System.out.println();
	}
}