递归实现合并两递增链表-合并后保持递增序列

java描述

数据结构：单链表

算法：递归

链表节点

package club.test;
/***
 * 链表节点
 * @author jiajia
 *
 */
public class Node {
	public int value;
	public Node next;
	public Node(int value, Node next) {
		super();
		this.value = value;
		this.next = next;
	}
}

算法实现

package club.test;
/**
 * 合并两个递增的链表
 * 合并后的链表保持递增序列
 * @author jiajia
 *
 */
public class TestMain {
	public static void main(String[] args) {
		Node list1=new Node(1,new Node(3,new Node(5,null)));
		//递增链表1
		Node list2=new Node(2,new Node(4,new Node(6,null)));
		//递增链表2
		Node n=Merge(list1, list2);
		//排序后的链表
		
		while(true) {
			if(n!=null) {
				System.out.print(n.value+" ");
				n=n.next;
				continue;
			}
			return;
		}
	}

	/**
	 * 核心算法
	 * @param list1 第一和递增链表
	 * @param list2 第二个递增链表
	 * @return 返回当前两个链表首节点最小的节点
	 */
	public static Node Merge(Node list1, Node list2) { 
		if (list1 == null) 
			return list2; 
		if (list2 == null) 
			return list1; 
		if (list1.value <= list2.value) { 
			list1.next = Merge(list1.next, list2); 
			return list1; 
		} else { 
			list2.next = Merge(list1, list2.next); 
			return list2; 
		} 
	}
}

案例输出:1 2 3 4 5 6