Hello, today we are going to look at a simple algorithm that involves a little bit of basic data structure. LeetCode’s problem 21 is merging ordered lists as usual

“Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.“

“Example“

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
Copy the code

The description is simple: given two sorted lists, merge them into a new list and return

For those of you who don’t know what a linked list is, just a quick review of what a linked list looks like in real life, what does a chain look like over here

In data structures, each pointer points to the next structure

Like hand in hand, A->B->C->D each child takes the next child’s hand. So, what’s the difference from an array? Arrays look like this too

First of all, you have to create a contiguous space in memory, and once you’ve created that space, it’s still there whether you use it or not, and if you suddenly run out of space, you can’t expand it, you just have to create a bigger one and put a smaller one in

The add/remove time for arrays is O(n), and the query time is O(1). So what’s the benefit of a linked list? “Dynamic Add, Add and delete” only needs to modify the adjacent elements of the element, equivalent to the time complexity of only “O(1)”.

So we haven’t even started talking about what a linked list actually looks like, but let’s take a picture, and use the official example as data. Okay

Does this look familiar to you? So what is this code

type ListNode struct {
 Val  int // Place the number in the image
 Next *ListNode // Where the pointer is in the picture
}
Copy the code

So you can see at a glance whether or not. After looking at the simple data structure, let’s look at the main code

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
 var head *ListNode
 var current *ListNode = new(ListNode)
 head = current
 forl1 ! =nil&& l2 ! =nil {
 if l1.Val < l2.Val {  current.Next = l1  l1 = l1.Next  } else {  current.Next = l2  l2 = l2.Next  }  current = current.Next  }  ifl1 ! =nil {  current.Next = l1  }  ifl2 ! =nil {  current.Next = l2  }  return head.Next } Copy the code

This time the code is the same, there’s no particularly complicated logic to pay attention to, but let’s split it up, okay

forl1 ! =nil&& l2 ! =nil {}
Copy the code

The first loop for is very clear, L1 and L2 can’t be empty and then let’s look at the first if

if l1.Val < l2.Val {
 current.Next = l1
 l1 = l1.Next
} else {
 current.Next = l2
 l2 = l2.Next } Copy the code

This one“Val“That’s the int part of our data structure, which stores a number, so let’s diagram the logic of that part

Given two official examples of linked listsWe create an empty list and point to the address of the empty list, head and current, in our code

Let’s go to the first if“L1<L2“In the case

It’s clear from the picture,“l1_0 < l2_0“It’s not true so it goes to the else branch so let’s see what happens when we go to the else branch

First let’s look at the code

current.Next = l2
Copy the code

Draw a graph by pointing current.Next to the current l2

And then the second sentence

l2 = l2.Next
Copy the code

Let’s remove l2_0 from its original stateIt looks something like this

Note that removing nodes requires freeing memory“Go has an internal Gabage Collection“Finally, we move current to the current.NEXT node

For our Next assignment, we can use current.Next = l1

After reading this, I believe you all understand the basic knowledge of linked lists, so let’s look at the following 2 If judgments

ifl1 ! =nil {
 current.Next = l1
}
ifl2 ! =nil {
 current.Next = l2
} Copy the code

What does this if mean here? What if, after we’re all done comparing, there’s something left in L1 or L2? “, pointing directly to the last element in the list is ok, because “the remaining elements must be larger than the previous element.”

After that, we go back to head.next. You see why we created a head in the first place? If the head of the list is missing, it is impossible to traverse the whole list, which is one of the disadvantages of the list


On this problem, there is a recursive solution, written more elegant, next time I will write you a recursive version, you can master both versions!

Come on!