[An Algorithm Question per Day] Merge two sorted linked lists

This column will start from the basics and progress step by step, brushing an algorithm question every day, and please support me a lot. Although the data structure is difficult, as long as you stick to it, you will be able to learn it well, and I hope everyone can benefit from it.
Column address: An algorithm question column every day Data Structure Column
Online brushing website: Niuke.com

Let's go!

foreword

• I recommend to everyone an artifact for writing questions and interviews. I also use this artifact to study! ~ The link is as follows: Brush question artifact jump link
• The artifact not only has a very beautiful web interface, but it is also very easy to operate and get started! It is very suitable for beginners to study systematically!
• Novices can use this artifact to do daily quizzes, read the facebooks of big factories, learn basic computer knowledge, and communicate face-to-face with Daniels~ The pictures of the quizzes have been placed below~

👀 Problem description

Topic source: Niuke.com

✏️ Thought analysis and problem solving
Solution 1, create a new linked list and a sentinel node (because there is no return, the sentinel node is required to record the position of the head node), traverse the two ordered linked lists list1 and list2, because the ascending order is required, then whoever takes the smaller will make the new linked list The next node, whichever node is taken, will be shifted backward until the trailing null.

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

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

if(list2==null){
return list1;
}
ListNode result = new ListNode(-1);
ListNode guard = result;//Sentinel node, very important
while(true){
if(list1 == null && list2 == null){//It's all over, it's over.
break;
}
if(list1==null){//After list1 is taken, all the following ones are taken from list2.
result.next = list2;
list2 = list2.next;
result = result.next;
}else if(list2 == null){//After list2 is taken, all the following ones are taken from list1.
result.next = list1;
list1 = list1.next;
result = result.next;
}else if(list1.val<=list2.val){//Like arrays, whoever takes the smaller
result.next = list1;
list1 = list1.next;
result = result.next;
}else if(list1.val>list2.val){//Like arrays, whoever takes the smaller
result.next = list2;
list2 = list2.next;
result = result.next;
}
}
return guard.next;
}

```

Solution 2: Optimize solution 1. It is observed that if you want to use up a linked list, you can directly point to its head node, omitting the step of taking the remaining nodes in solution 1.

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

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

if(list2==null){
return list1;
}
ListNode result = new ListNode(-1);
ListNode guard = result;
while(list1!=null && list2!=null){

if(list1.val<=list2.val){//Same solution one
result.next = list1;
list1 = list1.next;
result = result.next;
}else if(list1.val>list2.val){//Same solution one
result.next = list2;
list2 = list2.next;
result = result.next;
}
}

if(list1==null){//Optimization point, all remaining nodes take list2
result.next = list2;
}

if(list2==null){//Optimization point, all remaining nodes take list1
result.next = list1;
}
return guard.next;
}
}
```

The third solution is to use recursion. The idea is to compare the head nodes of list1 and list2 each time. Whoever is smaller is the head node, and then continues to compare. This step is the same for every step.

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

//Exit conditions
if(list1==null){
return list2;
}
//Exit conditions
if(list2==null){
return list1;
}

ListNode guard = null;
//Whoever is younger is the head node, and then continue to repeat this step
if(list1.val>=list2.val){
guard = list2;
guard.next = Merge(list1,list2.next);

}else{
guard = list1;
guard.next = Merge(list1.next,list2);

}
return guard;
}

```

After the article: The artifact of brushing questions