Linked List¶
I almost finished all the linked list questions, I found these things. . .¶
First up and down the outline of this article, this is a brain map I drew with mindmap, and then I will continue to improve, and gradually improve other topics.
You can also use vscode blink-mind to open the source file for viewing. There are some notes in it that you can click to open and view. The source files can be obtained by replying to the mind map on my public account "Like Plus", and the mind map will continue to update more content in the future. vscode plug-in address: https://marketplace.visualstudio.com/items?itemName=awehook.vscode-blink-mind
Hi everyone, my name is lucifer. The topic I bring to you today is "Linked List". Many people find linked lists to be a difficult topic. In fact, as long as you have the know-how, it is not that difficult. Next, let's talk about it.
Linked List Tag There are a total of 54 questions in leetcode. In order to prepare for this topic, I spent a few days reviewing almost all the linked list topics of LeetCode.
It can be seen that, except for the six locked ones, I brushed them all over. In fact, these six locked questions are not difficult, even similar to the other 48 questions.
By focusing on these questions, I found some interesting information, which I will share with you today.
Introduction¶
Various data structures, whether linear data structures such as queues and stacks or non-linear data structures such as trees and graphs, are fundamentally arrays and linked lists at the bottom. Regardless of whether you use an array or a linked list, all you use are computer memory. The physical memory is composed of memory units of the same size, as shown in the figure:
(Figure 1. Physical memory)
Although both arrays and linked lists use physical memory, they are very different in their use of physics, as shown in the figure:
(Figure 2. Physical storage diagram of arrays and linked lists)
It is not difficult to see that arrays and linked lists are just two ways of using physical memory.
The array is a continuous memory space, and usually the size of each unit is also fixed, so it can be randomly accessed by pressing the index. The linked list is not necessarily continuous, so its search can only rely on other methods, generally we traverse the search through a pointer called next. The linked list is actually a structure. For example, the definition of a possible singly linked list can be:
data is the data field, storing data, next is a pointer to the next node.
A linked list is a non-contiguous, non-sequential storage structure on a physical storage unit, and the logical order of data elements is realized through the link order of pointers in the linked list. The linked list is composed of a series of nodes (each element in the linked list is called a node), which can be dynamically generated at runtime.
From the above physical structure diagram, it can be seen that the array is a continuous space, and each item of the array is closely connected, so it is very troublesome to perform insert and delete operations. The time complexity of inserting and deleting the head of the array is both \(O(N)\), and the average complexity is also \(O(N)\), only the insertion and deletion of the tail is \(O(1)\). Simply put, "arrays are particularly friendly to queries, but not friendly to delete and add". In order to solve this problem, there is a data structure of linked list. Linked lists are suitable for scenarios where data needs to have a certain sequence, but frequent additions and deletions are required. For details, refer to the following section "Basic Operations of Linked Lists".
(Figure 3. A typical linked list logic representation diagram)
All the following figures are based on logical structure, not physical structure
The linked list has only one trailing node next, if it is a doubly linked list, there will also be a predecessor node pre.
Ever wondered why there is only a binary tree, but not a single tree. In fact, the linked list is a special tree, namely a fork tree.
Basic operation of linked list¶
To write the title of the linked list, it is necessary to be familiar with the basic operations and complexity of the linked list.
Insert¶
Insertion only needs to consider the position of the predecessor node and successor node to be inserted (in the case of a doubly linked list, the successor node needs to be updated), other nodes are not affected, so the operation time complexity of inserting with a given pointer is O(1). The pointer in the given pointer here refers to the predecessor node of the insertion position.
Fake code:
temp = the predecessor node of the position to be inserted.next
The predecessor node of the position to be inserted. next = pointer to be inserted
The pointer to be inserted. next = temp
If no pointer is given, we need to traverse to find the node first, so the time complexity is O(N) in the worst case.
Tip 1: Consider the case of head and tail pointers.
Tip 2: It is recommended for novices to draw pictures first, and then write code. After being proficient, naturally there is no need to draw pictures.
Delete¶
It is only necessary to correct the next pointer of the predecessor pointer of the node to be deleted to its next node, and pay attention to the boundary conditions.
Fake code:
The predecessor node of the position to be deleted.next = the predecessor node of the position to be deleted.next.next
Tip 1: Consider the case of head and tail pointers.
Tip 2: It is recommended for novices to draw pictures first, and then write code. After being proficient, naturally there is no need to draw pictures.
Traverse¶
The traversal is relatively simple, directly on the pseudo code.
Iterative pseudo code:
Current pointer = head pointer
while current node is not empty {
print(current node)
Current pointer = current pointer.next
}
A recursive pseudo-code for preorder traversal:
What is the difference between a linked list and an array?¶
Friends who are familiar with me should often hear me say that **array and linked list are also linear array structures. The two are the same for many conveniences, but they differ only in subtle operations and usage scenarios. That's it. It is difficult to directly investigate the usage scenarios in the topic.
In fact, the usage scenarios can be memorized by rote.
Therefore, for our questions, the difference between the two is usually only a slight operational difference. In this way, you may not feel strong enough. Let me give you a few examples.
Array traversal:
The traversal of the linked list:
Is it very similar?
**It can be seen that the logic of the two is the same, but the subtle operations are different. **such as:
-Array is index ++ -The linked list is cur = cur.next
What if we need to traverse in reverse order?
If it is a linked list, usually you need to resort to a doubly linked list. The doubly linked list has very few problems in buckle, so most of you have no way to get the predecessor node, which is why you often record a predecessor node pre by yourself.
If you add an element to the end of the array is:
In the case of linked lists, many languages do not have built-in array types. For example, Likou usually uses the following classes to simulate.
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {this.val = val;}
ListNode(int val, ListNode next) {this.val = val; this.next = next;}
}
We cannot call the push method directly. Think about it, if you are allowed to achieve this, how would you do it? You can think about it for yourself first, and then look down.
3...2...1
Ok, it's actually very simple.
// Assuming tail is the tail node of the linked list
tail.next = new ListNode('lucifer')
tail = tail.next
After the above two lines of code, tail still points to the tail node. Is it easy, have you learned it?
What's the use of this? For example, some problems require you to copy a new linked list. Do you need to open up a new linked list header and then continuously push the copied nodes? This is useful.
The bottom layer of the array is similar, a possible bottom layer implementation of array push:
To sum up, there are many similarities between array and linked list logic. The only difference is some usage scenarios and operation details. For the problem, we usually pay more attention to the operation details. Regarding the details, I will introduce to you next. This section mainly lets you know that the two are similar in thought and logic.
Some friends do the linked list question first, replace the linked list with an array, and then do it with an array. I don't recommend this approach. This is equivalent to denying the value of the linked list. Children should not imitate it.
How difficult is the linked list question?¶
Linked list questions are really not difficult. There is evidence that the linked list is not difficult. Take LeetCode platform as an example, there are only two difficult problems.
Among them, question 23 basically has no linked list operations, a conventional "merge sort" can be done, and merging two ordered linked lists is a simple question. If you know how to merge and sort arrays and merge two ordered linked lists, you should easily get this problem.
Merging two ordered arrays is also a simple problem, and the difficulty is almost the same.
As for question 25, I believe you can do it after reading the content of this section.
However, having said that, there are still many children who say to me that "the pointer goes around and I get dizzy", "there is always an endless loop". . . . . . Is the linked list problem really that difficult? How should we crack it? Lucifer has prepared a formula for everyone one principle, two question types, three attentions, and four skills, so that you can easily handle the linked list questions, and you will never be afraid of tearing the linked list by hand. Let's look at the content of this mantra in turn.
A principle¶
One principle is to draw pictures, especially for novices. Whether it is a simple question or a difficult problem, you must draw a picture. This is a guideline that runs through the list of questions.
Drawing pictures can reduce our cognitive burden. This is actually the same as writing drafts or memos. Putting things in your mind on paper. An improper example is that your brain is the CPU, and the memory of your brain is the register. The capacity of the register is limited. We need to put things that are not used frequently in the memory, and use the registers where they really should be used. This memory is everything you can draw pictures on, such as paper or a computer tablet.
It doesn't matter whether the painting is good or not, it just needs to be able to see clearly. Sketch it with a pen, and it's enough to be able to see the relationship.
Two test sites¶
I went through the linked watch of Likou. I found an interesting phenomenon, that is, the test point of the linked list is very single. In addition to design questions, the test center cannot be divided into two points:
-Modification of the pointer -Splicing of linked lists
Pointer modification¶
Among them, the most typical pointer modification is the inversion of the linked list. In fact, isn't the inversion of the linked list just to modify the pointer?
For a data structure such as an array that supports random access, it is easy to invert, and only needs to be exchanged continuously.
function reverseArray(arr) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const temp = arr[left];
arr[left++] = arr[right];
arr[right--] = temp;
}
return arr;
}
For linked lists, it is not so easy. There are simply not too many questions about reversing linked lists.
Today I wrote you the most complete linked list reversal, which can be used directly when you encounter it in the future. Of course, the premise is that everyone must first understand and then go for it.
Next, I want to achieve a reversal any piece of linked list
Where head refers to the head node that needs to be reversed, and tail is the tail node that needs to be reversed. It is not difficult to see that if head is the head of the entire linked list and tail is the tail of the entire linked list, then the entire linked list is reversed, otherwise it is the reverse partial linked list. Next, we will implement it.
First of all, all we have to do is draw a picture. I talked about this in the One Principle section.
The following figure shows the part of the linked list that we need to reverse:
And we expect it to look like this after the reversal:
It is not difficult to see that finally return to tail.
Due to the recursive nature of the linked list, in fact, we only need to reverse the two adjacent ones and use the same method to complete the rest.
Linked list is a recursive data structure, so the recursive thinking is often used to get twice the result with half the effort. The recursive thinking linked list will be expanded in the "Three Attentions" section later.
For two nodes, we only need to modify the pointer once, which seems not difficult.
It is this operation that not only creates a loop, but also makes you an endless loop. And let them part ways, which shouldn't be cut apart.
Regarding parting ways, this is not difficult to solve, we just need to record the next node before reversing:
What about the ring? In fact, the loop does not need to be resolved. Because if we traverse from front to back, in fact, the previous linked list has been reversed, so my picture above is wrong. The correct picture should be:
So far, we can write the following code:
# Flip a child linked list and return the new head and tail
def reverse(self, head: ListNode, tail: ListNode):
cur = head
pre = None
while cur != tail:
# Leave contact information
next = cur.next
# Modify pointer
cur.next = pre
# Continue going down
pre = cur
cur = next
# The new head and tail node after inversion is returned
return tail, head
If you observe carefully, you will find that our tail is actually not reversed. The solution is very simple, pass the node behind tail as a parameter.
class Solution:
# Flip a child linked list, and return the new head and tail
def reverse(self, head: ListNode, tail: ListNode, terminal:ListNode):
cur = head
pre = None
while cur != terminal:
# Leave contact information
next = cur.next
# Modify pointer
cur.next = pre
# Continue going down
pre = cur
cur = next
# The new head and tail node after inversion is returned
return tail, head
I believe you already have a certain understanding of the reversal linked list. We will explain this issue in more detail later, so please leave an impression first.
Linked list splicing¶
Have you found that linked watches always like to wear (splicing) around? For example, reverse linked list II, or merge ordered linked lists.
Why do linked watches always like to wear them around? In fact, this is the value of the existence of the linked list, and this is the original intention of designing it!
The value of the linked list is that it does not require the continuity of physical memory, as well as the friendliness of insertion and deletion. This can be seen in the physical structure diagram of the linked list and array at the beginning of the article.
Therefore, there are many splicing operations for the topic of the linked list. If you know the basic operation of the linked list I mentioned above, I believe this will not trouble you. Except for rings, borders, etc. . . _. We will look at these issues later.
Three Attentions¶
The most error-prone part of the linked list is where we should pay attention. 90% of the most common errors in linked lists are concentrated in the following three situations:
-A loop has appeared, causing an endless loop. -Unclear boundaries, leading to errors in boundary conditions. -Can't figure out how to do recursion
Next, let's look at them one by one.
Ring¶
There are two test sites in the ring:
-The question has the possibility of a ring, allowing you to judge whether there is a ring, and the location of the ring. -There is no ring in the question list, but the ring is closed by the pointer you manipulated.
Here we only discuss the second one, and the first one can use the fast and slow pointer algorithm mentioned later.
The simplest and most effective way to avoid loops is to draw a graph. If two or more linked list nodes form a loop, it is easy to see through the graph. Therefore, a simple practical technique is to draw a picture first, and then all pointer operations are reflected in the picture**.
But the linked list is so long, it is impossible for me to draw all of them. In fact, it is totally unnecessary. As mentioned above, the linked list is a recursive data structure. Many linked list problems are inherently recursive, such as reversing linked lists, so ** just draw a substructure. This knowledge, we will explain it in the **before and after part.
Border¶
What many people are wrong is not considering the boundary. One technique for considering boundaries is to look at the topic information.
-If the head node of the question may be removed, then consider using a virtual node, so that the head node becomes an intermediate node, and there is no need to make special judgments for the head node. -The title asks you to return not the original head node, but the tail node or other intermediate nodes. At this time, pay attention to the change of the pointer.
The specific content of the above two parts will be explained in the virtual header part that we will talk about later. Just leave an impression on the old rules.
Before and after¶
Ok, it's time to fill the hole. As mentioned above, the linked list structure is inherently recursive, so using recursive solution or recursive thinking will help us solve the problem.
In the Binary Tree Traversal section, I talked about three popular traversal methods of binary trees, which are preorder Traverse, middle-order traversal and post-order traversal.
The pre-middle-post order actually refers to the processing order of the current node relative to the child nodes. If the current node is processed first and then the child nodes are processed, then it is the preorder. If the left node is processed first, then the current node, and the right node is processed last, it is a middle-order traversal. The post-order traversal naturally processes the current node last.
In the actual process, we would not be so deducted and so dead. such as:
As in the above code, we have logic before **entering the left and right nodes, but also after **exiting the left and right nodes. What kind of traversal is this? Generally speaking, I am used to only looking at the position of the main logic. If your main logic is in the back, it is the post-order traversal, and if the main logic is in the front, it is the pre-order traversal. This is not the main point, it is not very helpful to us in solving the problem, but the content that will be discussed next is the most helpful to us in solving the problem.
Most of the questions are singly linked lists, and singly linked lists have only one successor pointer. Therefore, there are only pre-order and post-order, and no middle-order traversal.
Or take the classic reversal linked list mentioned above. If it is preorder traversal, our code is like this:
def dfs(head, pre):
if not head: return pre
next = head.next
# # Main logic (change pointer) behind
head.next = pre
dfs(next, head)
dfs(head, None)
The code for the subsequent traversal is like this:
def dfs(head):
if not head or not head.next: return head
res = dfs(head.next)
# The main logic (change the pointer) after entering the next node, that is, the process of recursive return will be executed to
head.next.next = head
head.next = None
return res
It can be seen that the two writing methods are not the same whether it is boundary, input parameter, or code. Why is there such a difference?
It’s not difficult to answer this question. You only need to remember a very simple sentence, that is, If it is a pre-order traversal, then you can imagine that the previous linked list has been processed, and you don’t have to worry about how to deal with it. . Correspondingly If it is a post-order traversal, then you can imagine that the following linked lists have been processed, and you don't have to worry about how to deal with it. The correctness of this sentence is also beyond doubt.
The following figure is what we should draw during the pre-order traversal. Just focus on the box (substructure) in the middle, and pay attention to two points at the same time.
- The previous ones have been processed
- The latter has not been dealt with yet
Based on this, it is not difficult for us to write the following recursive code, the code comments are very detailed, just look at the comments.
def dfs(head, pre):
if not head: return pre
# Leave the contact information (because none of the following has been processed, you can locate the next one through head.next)
next = head.next
# The main logic (change the pointer) is before entering the next node (because the previous ones have been processed, there will be no loop)
head.next = pre
dfs(next, head)
dfs(head, None)
What if it is a post-order traversal? The old rules, adhering to one of our principles, ** first draw a picture**.
It is not difficult to see that we can get the next element through head.next, and then point the next element of the next element to itself to complete the reversal.
Expressed in code is:
After drawing the picture, is it easy to see that there is a ring in the picture? Now you know the benefits of drawing, right? It's so intuitive. When you are very proficient, you don't need to draw, but before that, please don't be lazy.
Therefore, we need to change head.next to a value that does not cause a loop, such as blanking.
def dfs(head):
if not head or not head.next: return head
# No need to leave the contact information, because we have already passed by later, no need to go, now we are going back.
res = dfs(head.next)
# The main logic (change the pointer) after entering the next node, that is, the process of recursive return will be executed to
head.next.next = head
# Leave blank to prevent the generation of loops
head.next = None
return res
It is worth noting that preorder traversal can easily be transformed into iteration, so it is recommended that you use preorder traversal. Let me compare the iteration above with the preorder traversal here.
So why is it easy to transform preorder traversal into iteration? In fact, what I said is not accurate. To be precise, it should be that preorder traversal can easily be changed to recursion that does not require stacks, and subsequent traversals need to be completed with the help of stacks. This is not difficult to understand, because the main logic of the subsequent traversal is in the pop-up process of the function call stack, and the pre-order traversal is not required.
Here is a recursive technique for everyone. It is to imagine that we have processed part of the data and blocked them with our hands, but there is still a part waiting to be processed. Next, we will think about "how to use the processed data and the current Data to derive data that has not yet been processed" on the line.
Four tips¶
In response to the above test points and points of attention, I have summarized four skills to deal with, these are very practical skills in the usual practice.
Virtual Head¶
Before we come to understand the meaning of virtual heads, let's do a few quizzes for everyone.
Q1: What does the following code ans.next point to?
A1: The first head.
Q2: What does the following code ans.next point to?
A2: ListNode(4)
It doesn't seem to be difficult, let's continue to look at a question.
Q3: What does the following code ans.next point to?
A3: ListNode(3)
If you have answered all three questions correctly, congratulations, you can skip this part.
It doesn't matter if you don't understand it, I will explain it briefly here and you will understand.
What ans.next points to depends on where the last point to ans.next is cut off. For example, Q1, ans.next points to head, and we assume that the memory number it points to is 9527.
After executing head = head.next (ans and head are disconnected), the memory map at this time:
We assume that the memory address of the node pointed to by the next pointer of the head node is 10200
It is not difficult to see that ans has not changed.
For the second example. At the beginning, the same as the above example, they all point to 9527. Then executed:
Ans and head point to ListNode(3) at the same time. As shown in the figure:
head.next = ListNode(4) is the same. So the final pointer to ans.next is ListNode(4).
Let's look at the last one. The first half is the same as Q2.
According to the above analysis, the next of head and ans both point to ListNode(3) at this time. The key is the following two lines:
After pointing to head = ListNode(2), the relationship between head and ans is cut off. All current and subsequent head operations will not affect ans, so ans also points to the node before being cut off. So the output of ans.next is ListNode(3).
The reason for spending so much time on this thing is that pointer operations are the core of linked lists. If these basics are not understood, then it is difficult to do. Next, we introduce the protagonist-the virtual head.
I believe that the little friends who have made linked lists have heard of such a name. Why is it so easy to use? Its functions are nothing more than two:
-Turn the head node into an intermediate node to simplify judgment. -Return to the intermediate node of the linked list by breaking the link when appropriate.
I mentioned the three notes of the linked list above, one of which is the boundary. The head node is the most common boundary. If we use a virtual head to point to the head node, the virtual head is the new head node, and the virtual head is not the node given by the title and does not participate in the calculation, so no special judgment is required , The virtual head is for this purpose.
What if the question needs to be returned to a node in the middle of the linked list? In fact, virtual nodes can also be used. Due to the pointer operation I mentioned above, in fact, you can create a new virtual head, and then let the virtual head disconnect at the right time (just point to the node that needs to be returned), so that we can return to the next virtual head ok. 25. A group of K flip linked lists This technique is used.
This technique is often used not only in linked lists, but also in binary trees. For example, how do I ask you to return to the bottom left node of the binary tree? We can also use the techniques mentioned above. Create a new virtual node, the virtual node next points to the current node, and follow along, disconnect the link when recursive to the bottom left, and finally return to the next pointer of the virtual node.
Fast and slow pointer¶
Judge whether the linked list has a ring, and the entry of the ring can be solved by using fast and slow pointers. This kind of question just doesn't know whether it will be or not, and it will not be easy to forget if you know it. Not much to say, you can refer to my previous problem solution https://github.com/azl397985856/leetcode/issues/274#issuecomment-573985706.
In addition to this, finding the intersection point of the linked list is also a speed pointer, and the algorithm is similar. Otherwise, it's difficult if you don't know it, but easy if you know it. And next time you write it is not easy to be unexpected or make mistakes.
In this part, you can refer to the clarification of my problem above, and you can master it by writing one problem. Next, let's take a look at the ** method of threading and threading **.
In addition, because the linked list does not support random access, if you want to obtain specific elements such as the middle item and the last few items of the array, you need some special means, and this means is the speed pointer. For example, if you want to find the middle item of the linked list, you need to get two pointers, one big step (two steps at a time) and one small step (one step at a time)**, so that the fast pointer goes to the end and the slow pointer is just in the middle. If it is required to be the second to last in the linked list, then ** let the fast pointer go one step first, then the slow pointer **, so that the fast pointer goes to the end, and the slow pointer is just the second to last. This principle is not difficult to understand, right? This kind of technique is easy when you get to know it, and it is not easy to forget. It’s hard to come up with a type of **, so everyone has learned to practice a few questions and then put it down.
Thread the needle¶
This is the second test point of the linked list-** splicing linked list **. I am in 25. K a set of flipped linked lists, 61. Rotate Linked List and 92. Reverse Linked List II uses this method. Threading is a name I gave myself, and the advantage of naming is that it is easy to remember.
This method is usually not the optimal solution, but it is easy to understand, easy to write, and not easy to make mistakes. It is recommended for novices.
Take the reversal linked list as an example, but this time it is the middle part of the reversal linked list, so what should we do?
We have already talked about reversal, so I assume that the linked list has been reversed, so how to put the reversed linked list together?
The effect we want is this:
So how to achieve the effect on the picture? My approach is to number the breakpoints from the right. As shown in the figure, there are two breakpoints, involving a total of four nodes. So I numbered them a, b, c, d.
In fact, a and d are the predecessor and successor of the part of the linked list that needs to be reversed (not involved in the reversal), and b and c are the head and tail of the part that needs to be reversed (participated in the reversal).
Therefore, in addition to cur, use two pointers pre and next to find a, b, c, d.
Once you find it, it's easy, directly thread the needle and lead.
Isn't this all right? I remember 25 questions. Questions 61 and 92 are done in this way, clear and not confusing.
First wear and then row and then empty¶
This is the last of the four techniques. Although it is the last talk, it does not mean that it is unimportant. On the contrary, its practical value is great.
Continue back to the linked list reversal problem mentioned above.
cur = head
pre = None
while cur != tail:
# Leave contact information
next = cur.next
# Modify pointer
cur.next = pre
# Continue going down
pre = cur
cur = next
# The new head and tail node after inversion is returned
When do you need to determine whether next exists, and which one should be written first in the above two lines of code?
Is that so?
Still like this?
First wear¶
My advice to you is: wear it first. The thread here is to modify the pointer, including the modified pointer of the reversal linked list and the modified pointer of the needle thread. Don't worry about the order, wear first.
Second row¶
After wearing, the total number of codes has been determined, nothing more than permutation and combination to make the code bug-free.
Therefore, in the second step, the order is considered. Which of the above two lines of code comes first? It should be next = cur.next first, because cur.next changes after the latter statement is executed. Since the function of the above code is to reverse, then the linked list is actually disconnected after cur.next = pre, and the rest can not be accessed, which means that you can only return to the head node at this time.
In fact, if there are ten lines of passing code, we often don't need to consider them all. What we need to consider is only the part where the next pointer is changed. For example, the cur of cur.next = pre is changed to next. Therefore, where cur.next is used below, it is necessary to consider where to put it. No other code needs to be considered.
Null afterwards¶
Similar to the above principle, after wearing, the total number of codes has been determined, nothing more than to see which line of code will have a null pointer exception.
Like the above tips, we often don't need to consider them all. What we need to consider is only the part where the next pointer is changed.
Such as this code
We consider whether cur is empty? Obviously it is impossible, because the while condition is guaranteed, so there is no need to make a null.
So how is this code?
The above code has two nexts, the first one does not need to be blank, as already mentioned above. The second one is needed because next may be null. If next is null, a null pointer exception will be raised. Therefore, it needs to be modified to code like this:
The above are the four tips we give everyone. I believe that with these four skills, writing linked list questions will not be so difficult~ _
Topic recommendation¶
Finally, I recommend a few questions to everyone, and use the knowledge learned today to solve them~
-21. Merge two ordered linked lists -82. Remove duplicate elements in the sorted list II -83. Remove duplicate elements in the sorted list -86. Partition List -92. Reverse Linked List II -138. Copy linked list with random pointer -141. Linked List -142. Linked List II -143. Rearranged Linked List -148. Sort List -206. Reverse Linked List -234. Palindrome Linked List
to sum up¶
There is no big difference in logic between arrays and stacks. You see, the basic operations are similar. If it is a singly linked list, we cannot get the predecessor node in the time of \(O(1)\), which is why we always maintain a predecessor node when we traverse. But the essential reason is that the addition and deletion operations of the linked list all rely on the predecessor node. This is the basic operation of the linked list, which is inherently determined by the characteristics of the linked list.
Some students may have such a question. "You only talked about pointer modification and linked list splicing at the test site. Isn’t that enough for linked lists? Then why do I need to know the prefix and something for my questions? Didn't you cheat me?"
As I said earlier, the bottom layer of all data structures is one or both of arrays and linked lists. The linked list we are talking about here refers to the subject of investigating the basic operations of the linked list. Therefore, if you need to use merge sort to merge the linked lists in the topic, then the merge sort part is no longer in the scope of this article.
In fact, if you go to force button or other OJ flip-list questions, you will find that their linked list questions mostly refer to the question that the input parameter is a linked list and you need to perform some operations on the linked list. For another example, most of the topics of the tree are the input parameters are trees, and you need to search the topics on the tree. That is to say, there are very few problems that need to manipulate the tree (such as modifying the pointer of the tree). For example, there is a problem that allows you to add a right pointer to the tree to point to the right pointer of the same level. If it is the rightmost pointer, it points to empty .
The basic operation of the linked list is to add, delete, and check. Keep in mind that the basic operation and complexity of the linked list is the basic to solve the problem. Having these basics is not enough, everyone must keep in mind my formula "one principle, two test sites, three attentions, four skills".
To do linked list questions, if you want to get started, without it, only draw a tour. If you can draw a picture, and operate according to the picture, you will get started, regardless of whether the code you write has bugs.
There are only two core points of investigation in the topic of linked lists, one is pointer operation, and the typical one is reversal. The other is the splicing of linked lists. These two are not only the essence of the linked list, but also the main test points.
Knowing that the test sites are definitely not enough, where are we prone to make mistakes in writing code? What to pay attention to? Here I have listed three places that are easy to make mistakes, namely the ring, the boundary and the sequence.
The ring refers to the mutual references between nodes. If the problem of the ring itself has a ring, 90% of the double pointer can be solved. If there is no ring, then the ring is left when we manipulate the pointer. How to solve the problem of ring occurrence? That is to draw the picture, and then focus on the substructure, ignoring other information. **
In addition to the ring, another place that is easy to make mistakes is often the boundary condition, and the judgment of the boundary of the linked list head is a big one. To overcome this, we need to read the questions carefully, look at the requirements and return values of the questions, and another very useful technique is virtual nodes.
If you use recursion to solve the problems of the linked list, you must pay attention to whether you write the preorder or the postorder.
-If it is a pre-order, then ** just think about the sub-structure, the previous one has been processed, and how to deal with it, don't worry about it. If you have to ask, it's the same method. You don’t need to think about how to deal with the latter. If you have to ask, use the same method** -If it is a follow-up, then ** only think about the sub-structure, the latter has been processed, and how to deal with it, don't worry about it. If you have to ask, it's the same method. There is no need to consider how to deal with the previous ones. If you have to ask, use the same method**
If you want to write both recursion and iteration, I recommend you to use preorder traversal. Because the preorder traversal can easily be changed to recursion without stack.
The above is the entire content of the linked list topic. If you have any thoughts on this, please leave me a message. I will check the answers one by one when I have time. More algorithm routines can visit my LeetCode problem solution warehouse: https://github.com/azl397985856/leetcode. Currently it has 37K stars. You can also pay attention to my public account "Like Plus" to take you to the hard bones of algorithm.
The 1,000-page e-book that I have compiled has been developed and downloaded. You can go to the backstage of my public account "Likoujiajia" and reply to the e-book to get it.
