/**
 * 
 * 问题：合并两个有序的单链表
 *     给定两个有序单链表的头节点 head1和head2, 请合并两个有序链表， 合并后的链表依然有序，
 *     并返回合并后链表的头节点。
 * 	       例如：
 *	   0->2->3->7->null
 *     1->3->5->7->9->null
 *     合并后的链表为： 0-> 1->2->3->3->5->7->7->9->null
 * 
 * 解答：
 * 1.如果两个链表中有一个为空，说明无须合并过程， 返回另一个链表的头节点即可。
 * 
 * 2.比较head1和 head2的值， 小的节点也是合并后链表的最小节点 这个节点无疑应该是合并链表的头
 * 节点，记为 head; 在之后的步骤里， 哪个链表的头节点的值更小， 另一个链表的所有节点都会依次插
 * 入到这个链表中。
 * 
 * 3.不妨设 head节点所在的链表为链表 1,另一个链表为链表 2。链表 1和链表 2都从头部开始一起遍历，
 * 比较每次遍历到的两个节点的值， 记为 cur1和cur2, 然后根据大小关系做出不同的调整，同时用一个
 * 变量pre表示上次比较时值较小的节点。
 * 
 * 例如， 链表1为 1->5->6->null , 
 * 	         链表 2为 2->3->7->null。
 * 	  
 * 	      cur1=1,cur2=2, pre=null。cur1小于cur2, 不做调整， 因为此时 cur1较小，所以令
 * 	  pre=cur1=1,然后继续遍历链表 1的下一个节点， 也就是节点5。
 * 	      cur1=5,cur2=2, pre=1。cur2小于cur1,让 pre的 next指针指向 cur2,cur2的next
 * 	    指针指向 cur1。这样，cur2便插入到链表 1中。因为此时 cur2较小，所以令 pre=cur2=2,然后继续
 *   遍历链表 2的下一个节点， 也就是节点 3。这一步完成后， 链表1变为 1->2->5->6->null,链表2变为3->7->null。
 *   	  cur1=5, cur2=3, pre=2。cur1=5,cur2=3, pre=2。此时又是cur2较小，与上一步调
 *   整类似， 这一步完成后， 链表1变为1->2->3->5->6->null,链表2为7->null。
 *   	  cur1=5, cur2=7, pre=3。cur1=5, cur2=7, pre=3。cur1小于cur2,不做调整，因
 *   为此时cur1较小， 所以令pre=cur1=5, 然后继续遍历链表1的下一个节点，也就是节 点6。
 *        cur1=6, cur2=7, pre=5。cur1小于cur2, 不做调整， 因为此时cur1较小，所以令pre=cur1=6,
 *   此时已经走到链表1的最后一个节点， 再往下就结束， 如果链表1或链表2有任何一个走到了结束， 就进入步骤4。
 * 
 * 4.如果链表 1先走完， 此时cur1=null, pre为链表 1的最后一个节点， 那么就把 pre的 next指针指向链表2
 * 当前的节点（即cur2), 表示把链表2没遍历到的有序部分直接拼接到最后， 调整结束。如果链表2先走完， 说明链
 * 表2的所有节点都已经插入到链表l中，调整结束。
 * 
 * 5. 返回合并后链表的头节点head。
 * 
 * @author 雪瞳
 *
 */

　　

public class Node {

	public int value;
	public Node next;
	public Node(int data){
		this.value=data;
	}
}

　　

public class MergeNode {

	
	public Node mergeNode(Node head1,Node head2){
		
		if(head1 == null || head2 == null){
			return head1 == null?head2:head1;
		}
		Node head = head1.value<head2.value?head1:head2;
		
		// current 1 存储的是较小的元素
		// current 2 存储的是较大的元素
		Node current1 = head == head1 ? head1:head2;
		Node current2 = head == head1 ? head2:head1;
		// 存放当前current1和current2中最小的元素
		Node preCurrent = null;
		Node nextCurrent = null;
		
		while(current1 != null && current2 != null){
			
			if(current1.value <= current2.value){
				// 1 < 2 继续遍历直到出现 2 < 1 的情况
				preCurrent = current1;
				current1 = current1.next;
			}else{ 
				// 1 > 2 将节点2的当前元素插入到 1 中
				nextCurrent = current2.next;
				preCurrent.next = current2;
				current2.next = current1;
				
				preCurrent = current2;								
				current2 = nextCurrent;
			}
			
		}
		preCurrent.next = current1==null?current2:current1;
		
		return head;
	}
}

　　

public class TestMergeNode {

	public static void main(String[] args) {
		
		TestMergeNode test = new TestMergeNode();
		MergeNode merge = new MergeNode();
		
		Node n1 = new Node(1);
		Node n2 = new Node(2);
		Node n3 = new Node(3);
		Node n4 = new Node(4);
		Node n5 = new Node(5);
		Node n6 = new Node(6);
		Node n7 = new Node(7);
		Node n8 = new Node(8);
		Node n9 = new Node(9);
		
		n1.next = n2;
		n2.next = n3;
		n3.next = n4;
		n4.next = n5;
		Node head1 = n1;
		
		
		n6.next=n7;
		n7.next=n8;
		n8.next=n9;
		Node head2 = n6;
		
		test.showNodeList(head1);
		test.showNodeList(head2);
		Node result = merge.mergeNode(head1, head2);
		test.showNodeList(result);
	}
	/*获取链表
	public Node getNodeList(int length){
		Random rand = new Random();
		Node nodeArray[]= new Node[length];
		for(int i=0;i<length;i++){
			nodeArray[i]=new Node(rand.nextInt(10));
		}
		for(int i=0;i<length-1;i++){
			nodeArray[i].next = nodeArray[i+1];
		}
		return nodeArray[0];
	}*/
	//显示列表元素
	public void showNodeList(Node head){
		Node current = null;
		current = head;
		System.out.println("链表元素如下...");
		while(current!=null){
			System.out.print(current.value+"\t");
			current=current.next;
		}
		System.out.println();
	}
}