PROBLEM DESCRIPTION
Merge two sorted Linked List.
SOLUTION
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
public static Node mergeSortedLinkedList(Node h1, Node h2){
//If any of the list is empty, return the other sorted list
if(h1 == null) return h2;
if(h2 == null) return h1;
Node t=null, h3=null;
//Initialize
if(h1.value < h2.value){
t=h1;
h3=h1;
h1=t.next;
}else{
t=h2;
h3=h2;
h2=t.next;
}
while(h1 != null && h2 != null){
if(h1.value < h2.value){
t.next=h1;
h1=h1.next;
t=t.next;
}else{
t.next=h2;
h2=h2.next;
t=t.next;
}
}
if(h1 == null){
t.next = h2;
}else{
t.next = h1;
}
return h3;
}
RECURSIVE SOLUTION
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
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null && list2 == null) return null;
if(list1 == null) return list2;
if(list2 == null) return list1;
ListNode h1=list1;
ListNode h2=list2;
ListNode h3;
if(h1.val <= h2.val){
h3=h1;
ListNode t = h1.next;
h1.next = mergeTwoLists(t, h2);
}else{
h3=h2;
ListNode t = h2.next;
h2.next = mergeTwoLists(h1, t);
}
return h3;
}
}
BETTER RECURSIVE CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null)
return list2;
if(list2 == null)
return list1;
if(list1.val < list2.val){
list1.next = mergeTwoLists(list1.next, list2);
return list1;
}else{
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}
ANOTHER WAY TO CODE USING DUMMY HEAD
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
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead;
while(list1 != null && list2 != null){
int x = list1.val;
int y = list2.val;
if(x<y){
temp.next = list1;
list1 = list1.next;
}else{
temp.next = list2;
list2 = list2.next;
}
temp = temp.next;
}
if(list1 != null){
temp.next = list1;
}else{
temp.next = list2;
}
return dummyHead.next;
}
}