0%

合并两个已经有序的列表

问题描述

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

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
45
class ListNode {
int value;
ListNode next;
public ListNode(int value) {
this.value = value;
}
// 重写toString方法,使打印出来的东西比较正常
@Override
public String toString() {
StringBuilder stringBuffer = new StringBuilder();
stringBuffer.append(value+" ");
ListNode node = next;
while (node != null){
stringBuffer.append(node.value+" ");
node = node.next;
}
return stringBuffer.toString();
}
}
public ListNode merge(ListNode list1,ListNode list2) {
// 合并后的结果
ListNode res = null;
// 如果list1链表为空则返回list2
if(list1 == null){
return list2;
}
// 如果list2链表为空则返回list1
if(list2 == null){
return list1;
}

System.out.println("A链表 "+list1.toString());
System.out.println("B链表 "+list2.toString());
// 如果链表A的头节点小于B的节点,那么A的头节点将会是合并后的节点
// 然后去合并剩余的节点
// 链表B的头结点的值小于链表A的头结点的值,链表B的头结点是剩余结点的头结点,然后把这个结点和之前已经合并好的链表的尾结点链接起来
if(list1.value <= list2.value){
list1.next = merge(list1.next, list2);
return list1;
}else{
list2.next = merge(list1, list2.next);
return list2;
}
return res;
}

有的时候还需要将链表反转,逆序输出:

1
2
3
4
5
6
7
8
9
10
11
public ListNode reverse(ListNode node){
if (node == null || node.next == null) {
return node;// 若为空链或者当前结点在尾结点,则直接返回
}
//先反转后面的链表,走到链表的末端结点
ListNode reHead = reverse(node.next);
//再将当前节点设置为后面节点的后续节点
node.next.next = node;
node.next = null;
return reHead;
}