将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
程序员文章站
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;
}
}