欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-22 11:42:28
...
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;
	}
}

相关标签: 链表合并