将两个整型有序单向链表合成一个有序表

思路一：新建一个头节点，将原来的两个链表的节点依次插入到新节点之后~
（也有其他的思路，比如不新建一个头节点，直接在原来的基础之上进行交换，但是感觉思路以及实现上面没有第一个思路来得清晰简单。 以后再实现吧~）

一个bug 如果两个链表中有一个为空时 此时会出错
解决思路： 就检测第一个链表。如果为空，则直接返回第二个链表。无论第二个是否为空都行。


这个是节点

public class IntNode {
	int value;
	IntNode next;
	
	public IntNode(int value, IntNode next) {
		this.value = value;
		this.next = next;
	}
}

以下是main()方法

public class ListMerge {
	public static void main(String[] args) {
		//Linked List Construction
		
		IntNode a1 = new IntNode(1, null);
		IntNode a2 = new IntNode(2, null);
		IntNode a3 = new IntNode(7, null);
		
		IntNode b1 = new IntNode(3, null);
		IntNode b2 = new IntNode(4, null);
		IntNode b3 = new IntNode(8, null);
		
		a1.next = a2;
		a2.next = a3;
		b1.next = b2;
		b2.next = b3;
		
		IntNode head1 = a1;
		IntNode head2 = b1;
		
		//temp variables
		IntNode t = null;
		
		//create new head
		IntNode head = null;
		if(head1.value < head2.value) {
			head = head1;
			head1 = head1.next;
		} else {
			head = head2;
			head2 = head2.next;
		}
		head.next = null;
		t = head;
		
		
		//merge into new linked list
		while( head1 != null && head2 != null ) {
			if(head1.value < head2.value) {
				t.next = head1;
				head1 = head1.next;
			} else {
				t.next = head2;
				head2 = head2.next;
			}
			t = t.next;
			t.next = null;
		}
		
		//merge left ones
		if(head1 != null) {
			t.next = head1;
		} else if(head2 != null){
			t.next = head2;
		}
		
		//free space
		head1 = null;
		head2 = null;
		
		//print all nodes
		t = head;
		while(t != null) {
			System.out.print(t.value + " ");
			t = t.next;
		}
	}
}