将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

package leetcode;

/**
 * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
 * 示例：
 * 输入：1->2->4, 1->3->4 
 * 输出：1->1->2->3->4->4
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author Administrator
 */
public class Test {
	static class Node{
		int val;
		Node next;
		Node (int x){
			val = x;
		}
	}
	public static void main(String[] args) {
		Node n1 = new Node(1);
		Node temp1 = n1;
		System.out.println("n1链为：-----------");
		System.out.println(n1.val);
		for (int i = 2; i < 7; i++) {
			temp1.next = new Node(i);
			temp1 = temp1.next;
			System.out.println(temp1.val);
		}
		System.out.println("--------------");
		Node n2 = new Node(2);
		Node temp2 = n2;
		System.out.println("n2链为：-----------");
		System.out.println(n2.val);
		for (int i = 4; i < 12; i=i+2) {
			temp2.next = new Node(i);
			temp2 = temp2.next;
			System.out.println(temp2.val);
		}
		System.out.println("--------------");
		Node n3Result = mergeTwoLists(n1, n2);
		Node temp = n3Result;
		while(true){
			if(temp.next!=null){
				System.out.println(temp.next.val);
				temp =temp.next;
			}else {
				break;
			}
		}

	}
	private static Node mergeTwoLists(Node n1,Node n2) {
		Node newNode = new Node(0);
		Node cur = newNode;
		while(n1!=null && n2!=null) {
			if(n1.val < n2.val) {
				cur.next = n1;
				cur = cur.next;
				n1 = n1.next;
			}else {
				cur.next = n2;
				cur = cur.next;
				n2 = n2.next;
			}
		}
		//任一为空，直接连接另条表
		if(n1 == null) {
			cur.next = n2;
		}else {
			cur.next = n1;
		}
		return newNode;
	}
}