# 【LeetCode - Java】21. Merge two ordered linked lists (simple)

2022-01-26 22:10:04 Beeemo

## 2. Their thinking

This kind of topic belongs to classic data structure Class title , understand Linked list After the feature, it's good to start . First Conventional thinking There are two kinds of , One is Make elements in a list Insert To another linked list to form an ordered linked list that meets the requirements ; another The train of thought is Generate a new linked list , Put the elements that meet the requirements in the two old linked lists add to To the new linked list .

Plug in processing relative Generative expressions are a little more troublesome , You need to determine Which old linked list to use as the benchmark , According to the requirements of this topic, you should choose Small opening element The linked list is used as the insertion benchmark , Before that, we need to Judge not empty , Otherwise it will appear Null pointer exception .

in addition to , This topic can also be based on recursive The mind of . Recursive function Is to find out At present Nodal Elements as well as The subsequent Of Sublist , This kind of thinking is actually Be similar to Plug in processing ideas .

## 3. Code implementation

### 3.1 Plug in

``````public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

ListNode pre;
ListNode list;
if(list1==null)
return list2;
else if(list2==null)
return list1;
else if (list1.val < list2.val) {

list = list1;
list1 = list1.next;
} else {

list = list2;
list2 = list2.next;
}
pre = list;
while (list1 != null && list2 != null) {

if (list1.val < list2.val) {

pre.next = list1;
list1 = list1.next;
} else {

pre.next = list2;
list2 = list2.next;
}
pre = pre.next;
}
pre.next = list1 == null ? list2 : list1;
return list;
}
``````

### 3.2 Generative

``````public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

ListNode pre;
ListNode list = new ListNode();
pre = list;
while (list1 != null && list2 != null) {

if (list1.val < list2.val) {

pre.next = list1;
list1 = list1.next;
} else {

pre.next = list2;
list2 = list2.next;
}
pre = pre.next;
}
pre.next = list1 == null ? list2 : list1;
return list.next;
}
``````

### 3.3 Recursive

``````public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

if (list1 == null)
return list2;
else if (list2 == null)
return list1;
else {

if (list1.val < list2.val) {

list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {

list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}
``````

This implementation is the subject Relatively optimal performance Solution method .

### 3.4 contrast

Of the above three methods Time complexity All are O(m+n),m and n They are the of two linked lists length , Therefore, the time performance of the three algorithms There is no difference . And in the Spatial complexity On , Generative algorithm because it needs to generate New linked list , Therefore, compared with other algorithms in terms of space occupation Bigger . Recursive Although the solution is feasible in this subject , Because the number of nodes in this topic does not exceed 50, But if the number of nodes is too large Prone to stack overflow The situation of .