我有一壶酒,足以慰平生。

0%

力扣每日一题之合并两个有序链表

1、题目描述

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

2、示例

1
2
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

3、思路

在循环中比较两个升序链表的节点元素大小,将值较小的节点(必定是表头)移除,添加至new的节点后面。当其中一条链表为null时,将另一条链表接在重排序的链表后面,排序完成,但是多出一个新创建的头节点,故输出listNode4.next。

4、代码及测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package com.lcx.leetCode;

import javax.xml.soap.Node;

public class Demo21 {
public static ListNode4 mergeTwoLists(ListNode4 l1, ListNode4 l2) {
ListNode4 listNode4 = new ListNode4(-1);
ListNode4 re = listNode4;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
re.next = l1;
l1 = l1.next;
}else {
re.next = l2;
l2 = l2.next;
}
re = re.next;
}
re.next = l1 == null ? l2 : l1;
return listNode4.next;
}

public static void main(String[] args) {
ListNode4 node = new ListNode4(1);
ListNode4 node1= new ListNode4(2);
ListNode4 node2 = new ListNode4(4);
node.next = node1;
node1.next = node2;

ListNode4 nod = new ListNode4(1);
ListNode4 nod1= new ListNode4(3);
ListNode4 nod2 = new ListNode4(4);
nod.next = nod1;
nod1.next = nod2;

ListNode4 node4 = mergeTwoLists(node, nod);
while (node4.next != null){
System.out.println(node4.val);
node4 = node4.next;
}
System.out.println(node4.val);

}
}

测试结果:

image-20200621160908070

代码已上传至github

您的支持是我继续创作的动力