21.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
（友情链接 —>Java数据结构和算法（七）——链表 )
首先先看看怎么做这道题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/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l2 == null){
return l1;
}
if(l1 == null){
return l2;
}
ListNode temp;
if (l1.val < l2.val){
temp = l1;
temp.next = mergeTwoLists(l1.next,l2);
}else{
temp = l2;
temp.next = mergeTwoLists(l1,l2.next);
}
return temp;
}
}
首先我们要知道Java链表是个啥玩意，先看个实例：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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119import javax.xml.soap.Node;
public class SingleLinkedList {
private int size;
private Node head;
public SingleLinkedList() {
size = 0;
head = null;
}
//链表的每个节点类
private class Node{
private Object data;
private Node next;
public Node(Object data) {
this.data = data;
}
}
//在链表头添加元素
public Object addHead(Object obj) {
Node newHead = new Node(obj);
if(size == 0) {
head = newHead;
}else {
newHead.next = head;
head = newHead;
}
size++;
return obj;
}
//在链表头删除元素
public Object deleteHead() {
Object obj = head.data;
head = head.next;
size--;
return obj;
}
//查找指定元素，找到了返回Node,找不到返回null
public Node find(Object obj) {
Node current = head;
int tempSize = size;
while(tempSize > 0) {
if (obj.equals(current.data)) {
return current;
}else {
current = current.next;
}
tempSize--;
}
return null;
}
//删除指定的元素，删除成功返回true
public boolean delete(Object value) {
if(size == 0) {
return false;
}
Node current = head;
Node previous = head;
while(current.data != value) {
if(current.next == null) {
return false;
}else {
previous = current;
current = current.next;
}
}
if(current == head) {
head = current.next;
size--;
}else {
previous.next = current.next;
size--;
}
return true;
}
//判断链表是否为空
public boolean isEmpty() {
return (size == 0);
}
//显示节点信息
public void display() {
if (size > 0) {
Node node = head;
int tempSize = size;
if(tempSize == 1) {//当前链表只有一个节点
System.out.println("["+node.data+"]");
return;
}
while(tempSize > 0) {
if(node.equals(head)) {
System.out.print("["+node.data+"->");
}else if(node.next == null) {
System.out.print(node.data+"]");
}else {
System.out.print(node.data+"->");
}
node = node.next;
tempSize--;
}
System.out.println();
}else {
System.out.println("[]");
}
}
}
定义
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
单链表(我这种菜鸡只能谈论这种最简单的链表了)
单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。而插入一个节点，对于单向链表，我们只提供在链表头插入，只需要将当前插入的节点设置为头节点，next指向原头节点即可。删除一个节点，我们将该节点的上一个节点的next指向该节点的下一个节点。
关于本题
那么结合本题，我们可以从题意中得知，要把valu小的放在前。
- 第一步，传进两个链表
- 第二步，判断哪个是空，一个空，返回另一个
- 第三步，声明一个新的链表temp作为中间链表
- 如果l1.valu < l2.valu
- temp = l1
- temp.next的地址则需要通过递归进行新一轮的比较，所以temp.next = mergeTowLists(l1.next, l2)
……
- else
- temp = l2
- temp.next的地址则需要通过递归进行新一轮的比较，So, temp.next = mergeTowLists(l1, l2.next)
……
- 如果l1.valu < l2.valu
- 第四步，以上递归进行完了，就可以将最终的temp返回了。