-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeTwoList.java
More file actions
111 lines (101 loc) · 2.69 KB
/
Copy pathMergeTwoList.java
File metadata and controls
111 lines (101 loc) · 2.69 KB
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
package linklist;
public class MergeTwoList {
/**
* 复杂写法
*
* @param node1
* @param node2
* @return
*/
public static ListNode merge(ListNode node1, ListNode node2) {
if (node1 == null) {
return node2;
}
if (node2 == null) {
return node1;
}
ListNode dummy1 = new ListNode(0);
dummy1.next = node1;
ListNode dummy2 = new ListNode(0);
dummy2.next = node2;
ListNode result = node1.val < node2.val ? node1 : node2;
ListNode current1 = dummy1.next;
ListNode next1 = current1;
ListNode current2 = dummy2.next;
ListNode next2 = current2;
while (current1 != null && current2 != null) {
if (current1.val < current2.val) {
next1 = current1.next;
current1.next = current2;
current1 = next1;
} else if (current1.val > current2.val) {
next2 = current2.next;
current2.next = current1;
current2 = next2;
} else {
next1 = current1.next;
next2 = current2.next;
current1.next = current2;
current1 = next1;
current2 = next2;
}
}
return result;
}
/**
* 简洁写法
*
* @param node1
* @param node2
* @return
*/
public static ListNode merge2(ListNode node1, ListNode node2) {
if (node1 == null) {
return node2;
}
if (node2 == null) {
return node1;
}
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (node1 != null && node2 != null) {
if (node1.val < node2.val) {
current.next = node1;
node1 = node1.next;
} else {
current.next = node2;
node2 = node2.next;
}
current = current.next;
}
if (node1 != null) {
current.next = node1;
}
if (node2 != null) {
current.next = node2;
}
return dummy.next;
}
/**
* 递归写法
*
* @param node1
* @param node2
* @return
*/
public static ListNode merge3(ListNode node1, ListNode node2) {
if (node1 == null) {
return node2;
}
if (node2 == null) {
return node1;
}
if (node1.val < node2.val) {
node1.next = merge3(node1.next, node2);
return node1;
} else {
node2.next = merge3(node1, node2.next);
return node2;
}
}
}