See the “Data Structures & Algorithms” series: 1. Introduction # Plan your Route
6. Linked lists (PART 1)
This article is the next part of a series of articles on linked lists. It will focus on some classic problems of linked lists and summarize some skills of solving linked lists.
Are you itching to try it? 2) ㅂ•́)و✧
Understand “Pointers”
It’s not hard to understand the structure of a linked list, but adding Pointers makes it confusing. So, in order to write good list code, we must first understand “Pointers”.
Pointer concepts and corresponding types exist in C language and Golang, but some languages do not have Pointers and instead use “references”, such as Java and Python. Whether “pointer” or “reference”, in fact, they mean the same thing, they are the memory address of the object referred to.
Focus on the following concepts:
Assigning a variable to a pointer is essentially assigning the memory address of the variable to the pointer.
Conversely, if the variable’s memory address is stored in the pointer, the variable can be found through the pointer.
Next, we will deepen our understanding of “Pointers” through some simple single linked list operations: deleting, inserting, and swapping nodes.
Delete nodes
Removes a given (non-trailing) node from a linked list. The only argument passed to the function is the node to be deleted
Refer to LeetCode 237. Remove nodes from linked lists
In the first part of the linked list, the idea is to change the Next point of the node leading A, but the node leading A of B is unknown, how to do?
Now, if you’re familiar with Pointers, you can see that changing b to C becomes (premise: b is not a trailing node).
One line of code to fix, is not super simple ~ (annotation method can also be, it is the official solution of LeetCode)
Type ListNode struct {* Val int * Next *ListNode *} */
func DeleteNode(dNode *ListNode) {
*dNode = *dNode.Next
// dNode.Val = dNode.Next.Val
// dNode.Next = dNode.Next.Next
}
Copy the codePlay.golang.org/p/SsD42moMy… If you try to delete the end node, what happens?
Why not delete the end node? Think about it for yourself
Insert the node
Insert a node after some node, that’s not too hard to do
func InsertAfterNode(iNode *ListNode, val int) {
insertNode := new(ListNode)
insertNode.Val = val
insertNode.Next = iNode.Next
iNode.Next = insertNode
}
Copy the codePlay.golang.org/p/xgHz7qk4o…
What about inserting a node before a node? It’s just a value swap
func InsertBeforeNode(iNode *ListNode, val int) {
insertNode := new(ListNode)
insertNode.Val = iNode.Val
iNode.Val = val
insertNode.Next = iNode.Next
iNode.Next = insertNode
}
Copy the codeSwitching nodes
Given a node, swap it with a subsequent node (non-tail node)
With the experience of removing inserts, it’s not that difficult, and you can take advantage of the two existing methods.
For example, if b and C want to switch (b comes before C), we can add node B after node C and delete node B before node C.
func ExchangeNode(cNode *ListNode) {
InsertAfterNode(cNode.Next, cNode.Val)
*cNode = *cNode.Next
}
Copy the codePlay.golang.org/p/A8m-_gGqR…
Once you’ve mastered the concept of Pointers or references, the linked list code is at least as easy to read as possible
Reference below: LeetCode linked list — Classic problem
A classic problem
Reverse a linked list
First to a classic high-frequency interview 🌰, how to reverse a single linked list?
Input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL
Output: 5 – > 4 – > 2 – > 3 – > 1 – > NULL
Instead of writing it, what would you do if you just thought about pointer changes?
Some people might think: iterate through the list, reach the tail, store the tail in the new list, delete the tail of the original list, and continue recursive operations until the original list is empty.
(it’s even… This might be the solution for people who are used to array manipulation.
What’s the complexity? n + n-1 + … + 1 => O(n²), plus additional space complexity O(n), if the interview answer this probability is GO (GameOver😂)
Linked lists, we need to take advantage of easy insert/delete, reduce the disadvantage of lookup.
One solution is as follows: iterate in the original order, moving the nodes to the first node until the last node ends.
It should be easier to understand (red arrows indicate nodes to be iterated over) :
The time complexity is O(n). In addition, only constant level extra space is used, so the space complexity is O(1).
With the idea in mind, the code will follow (see 206 for similar ideas in other languages). Reverse linked list)
⚠️⚠️ Note the empty list judgment
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
var prev *ListNode
curr := head
forcurr ! =nil {
tmp := curr.Next
curr.Next = prev
prev = curr
curr = tmp
}
return prev
}
Copy the codePlay.golang.org/p/gD_uCUI83…
Reverse linked list is really a favorite interview test, this question looks easy, but it is not easy to use two ways to go through the bug free.
The question is, what else can you think of? Like recursion? Refer to LeetCode 206 for solutions
Array conversion linked list
The above example code uses an exhaustive method to add linked list elements, which is obviously a bit inefficient.
Given an array [1, 2, 6, 3, 4, 5, 6], how do you convert an array to a linked list?
This is not really an algorithmic category, but you need to understand the structure of linked lists. Golang references the following:
func Ints2LinkedList(nums []int) *ListNode {
if len(nums) == 0 {
return nil
}
l := &ListNode{}
t := l
for _, v := range nums {
t.Next = &ListNode{Val: v}
t = t.Next
}
return l.Next
}
Copy the codeThe logic implemented in other languages is similar, and the analysis steps are as follows:
- Empty array, return directly
nil - Define an empty linked list L, where pointer T points to the list memory address,
- Iterate over nums
- Set Val:v, Next: &ListNode{Val: v} to Next =, and store the memory address to Val
- The pointer T moves to the last digit until the array is traversed completely
Example code for the above: play.golang.org/p/xH8TU7_1Z… ; Reference: Big guy’s solution
Individual original solution: play.golang.org/p/CwRYrDxUP… ; It’s not like the big guy
So the question is, how do you convert a list to an array? If you’re interested, you’ll understand. ◕ ‿ ‿ ◕.) づ
Removes a linked list element
Deletes all nodes in the linked list that are equal to the given value val.
Input: 1 – > 2 – > 6 – > 3 – > 4 – > 5 – > 6 – > NULL, val = 6 output: 1 – > 2 – > 3 – > 4 – > 5 > NULL
Here are two ideas:
Next (currentNode.next-next) ==val (currentNode.next-next)
Note, however, that the direction of the header changes (only if head.Val == Val).
See the Golang code as follows (for other languages see 237. Delete nodes in the linked list) :
func RemoveElements(head *ListNode, val int) *ListNode {
forhead ! =nil && head.Val == val {
head = head.Next
}
if head == nil {
return head
}
curr := head
forcurr.Next ! =nil {
if curr.Next.Val == val {
curr.Next = curr.Next.Next
} else {
curr = curr.Next
}
}
return head
}
Copy the codePlay.golang.org/p/-QjWV4drw…
The second, recursive method, is a little difficult to understand, please refer to the solution of LeetCode, which also provides some other methods
func RemoveElements(head *ListNode, val int) *ListNode {
if head == nil {
return head
}
head.Next = RemoveElements(head.Next, val)
if head.Val == val {
return head.Next
}
return head
}
Copy the codePlay.golang.org/p/OtXnPRk2N…
Parity linked list
Given a single linked list, rank all the odd and even nodes together. Note that the odd and even nodes refer to the parity of node numbers, not the parity of node values.
Try using the in situ algorithm. The space complexity of your algorithm should be O(1), and the time complexity should be O(Nodes), which is the total number of nodes.
Example 1:
Input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL
Output: 1 – > 3 – > 5 – > 4 – > 2 – > NULL
Example 2:
Input: 1 – > 2 – > 3 – > 5 – > 4 – > 7-6 – > > NULL
Output: 2 – > 3 – > 6-7-1 – > > > 5 – > 4 – > NULL
Description:
The relative order of odd and even nodes should be preserved. The first node in the list is considered an odd number, the second is considered an even number, and so on.
Similarly, to continue the idea of iteration, first draw the following diagram (mainly consider how Pointers move and how nodes operate).
We can separate the odd and even chains and then connect them in series, as shown in figure 328. Parity linked list
Follow the logic of your thoughts and start doing it
func OddEvenList(head *ListNode) *ListNode {
if head == nil {
return head
}
evenHead := head.Next
odd := head
even := evenHead
foreven ! =nil&& even.Next ! =nil {
odd.Next = even.Next
odd = odd.Next
even.Next = odd.Next
even = even.Next
}
odd.Next = evenHead
return head
}
Copy the codePlay.golang.org/p/n3EZdaVvx…
Palindrome list
Determine if a linked list is palindromic. 234. Palindrome linked list
Example 1:
Input: 1 – > 2
Output: false
Example 2:
Input: 1 – > 2 – > 2 – > 1
Output: true,
Advanced: Can you solve this problem with O(n) time complexity and O(1) space complexity?
Method 1: Record the value of the linked list, which can be considered as an array (previous extended thinking). We then iterate over the values of the comparison array.
O(n) +O(n /2) => O(n), space +O(n)
func isPalindrome(head *ListNode) bool {
vals := []int{}
forhead ! =nil {
vals = append(vals, head.Val)
head = head.Next
}
n := len(vals)
for i, v := range vals[:n/2] {
ifv ! = vals[n- 1-i] {
return false}}return true
}
Copy the codePlay.golang.org/p/etaWnP1oJ…
Method 2: Recursive implementation, however, time and space complexity still requires O(n)
func isPalindrome(head *ListNode) bool {
frontPointer := head
var recursivelyCheck func(*ListNode) bool
recursivelyCheck = func(curNode *ListNode) bool {
ifcurNode ! =nil {
if! recursivelyCheck(curNode.Next) {return false
}
ifcurNode.Val ! = frontPointer.Val {return false
}
frontPointer = frontPointer.Next
}
return true
}
return recursivelyCheck(head)
}
Copy the codeMethod 3: Reverse the second half of the list (modify the structure of the list) and then compare the first half to the second half
After the comparison is complete, we should restore the linked list. Although a test case can pass without recovery, people who use this function usually don’t want the list structure changed.
Although this method can reduce the space complexity to O(1), it also has disadvantages in concurrent environment. In a concurrent environment, the function needs to lock access to the list from other threads or processes while it is running, because the list can be modified during the execution of the function.
And then what? What? The space complexity can be reduced to O(1) with double pointer record & contrast. Ah, very tired, (￣▽￣)و
func reverseList(head *ListNode) *ListNode {
var prev, cur *ListNode = nil, head
forcur ! =nil {
nextTmp := cur.Next
cur.Next = prev
prev = cur
cur = nextTmp
}
return prev
}
func endOfFirstHalf(head *ListNode) *ListNode {
fast := head
slow := head
forfast.Next ! =nil&& fast.Next.Next ! =nil {
fast = fast.Next.Next
slow = slow.Next
}
return slow
}
func isPalindrome(head *ListNode) bool {
if head == nil {
return true
}
// Find the last node of the first half of the list and reverse the last half of the list
firstHalfEnd := endOfFirstHalf(head)
secondHalfStart := reverseList(firstHalfEnd.Next)
// Check whether palindromes exist
p1 := head
p2 := secondHalfStart
result := true
forresult && p2 ! =nil {
ifp1.Val ! = p2.Val { result =false
}
p1 = p1.Next
p2 = p2.Next
}
// Restore the list and return the result
firstHalfEnd.Next = reverseList(secondHalfStart)
return result
}
Copy the codeSkills summary
Master the pointer
To write linked list code correctly, you must first understand Pointers. The memory usage of a computer system is worth exploring if you want to trace it back to its roots.
For the grasp of linked list Pointers, this article begins with a focus and examples, not skilled on the practice, review the new.
Note pointer loss
⚠️⚠️
Pointer confusion is a relatively easy problem, beginners including me… It’s often chaotic.
For example, when inserting nodes, be careful about the order of operations.
For some languages, such as C, memory management is the responsibility of the programmer, and if the node is not manually freed, memory leaks will occur. This should be paid more attention to
Similarly, when deleting linked list nodes, you must also remember to manually free up memory space, otherwise, memory leaks will also occur. Of course, for a programming language like Java, where the VIRTUAL machine automatically manages memory, this is not a concern.
Mind the boundary treatment
Code is most prone to bugs in some boundary or exception situations. Is there any care to check boundary conditions during code writing? This is very important, often determines the quality of development ability, which is also in the interview, the interviewer will pay attention to the point of investigation.
So, usually in writing methods or functions, you start with nullation. (See the previous example)
The boundary conditions for checking the correctness of linked list code are usually the following:
- When the linked list is empty
- A linked list contains only one node
- A linked list contains only two nodes
- When the code logic deals with the headers and the endpoints
In fact, this kind of “boundary-checking” routine applies to almost any code inspection, which is also the domain of “boundary-value testing.”
Analyze as much as you can about what boundary or exception cases you’ll encounter and how to deal with them so that your code is robust!
Draw pictures to help you think
Complex algorithm problems, often need to first example and drawing, especially like linked lists such as Pointers.
It’s not a shame to draw a draft, it doesn’t matter if it looks good or not, it’s the absolute truth to solve the problem.
Have you noticed that there is an example above specially accompanied by a manuscript? Multicolor pen AIDS can help clarify our thinking (especially dual Pointers).
After the preparation of double Pointers (fast and slow Pointers), a special chapter is organized to do the integration of similar algorithm skills.
In fact, this kind of problem is probably not thinking at first glance, but once you know it is not easy to forget.
Such as to determine whether the list has a ring, and the entrance of the ring, such as 141
Secondly, after writing the code, you can also take a few examples, draw on the paper, walk through the code, it is easy to find the Bug in the code.
Recursive thinking
Many operations in the linked list can be completed by using “recursive” logical thinking.
In fact, “recursion” also needs practice, but here is just a glimpse of the examples. The temporal and spatial complexity of recursion is more difficult to understand and analyze. .
After preparation, “recursive algorithm” was specially sorted out, mainly explaining the algorithm ideas and complexity analysis of recursion. Come back to the list problems and recurse again