“This is the 10th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
Let’s start with a scene
- Turn on the force snap brush algorithm
- A list of simple problems, full of confidence, directly began to masturbation code
- Backhand a submission, directly error
- Then began to look for bugs, looking for a long time or error
- Finally the mentality collapsed, closed the force button to continue to touch the fish…
The above is the situation I encountered at the beginning of the brush problem. In fact, when doing linked list problems, it is best to clear your mind by drawing pictures, otherwise it is easy to confuse yourself. Let’s look at some algorithms related to reverse linked lists.
Let’s start with the easy ones
206. Reverse linked lists
Analysis of the
- Given by the problem
Example 1
So, for example, if you want to get an inverted list then1 nodes
Will eventually point tonull
- So let’s create a new pointer
p
Point to thenull
- Create another one
q
Pointer tohead
Convenient reversal operation later
- If you want to
1 nodes
Point to thenull
Cannot be directly modifiedq.next = p
, this will break the linked list, lost from2 nodes
The opening quote. Need a variable to receive, so willhead
Move backwards get2 nodes
The reference,head = head.next
- You can do it right now
1 nodes
thenext
Point to thenull
.q.next = p
- then
p
andq
The needle moves back,p = q
.q = head
, avoid the assignment order can not be reversed, so complete1 nodes
The reversal of the
- Repeat the above steps to complete the inversion. Take a look at the GIF
- The last return
Pointer to the p
It’s a linked list reversed
Code implementation
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @return {ListNode}* /
var reverseList = function(head) {
var p = null, q = head
while(q) { // The order cannot be reversed, otherwise references will be lost
head = head.next
q.next = p
p = q
q = head
}
return p
};
Copy the code
- It’s easy to write code based on the above image analysis, so make it more difficult
Advanced intermediate problems
92. Reverse linked list II
Analysis of the
- With the experience of the previous problem, this problem only adds the position and number of inversion, and does not need to reverse the whole list. The main focus is, how to break the list into partial inversion, and then connect back to the original list
- In order to
Example 1
For example, first define a virtual head noderet
Point to thehead
The purpose is to make it easy to return, because you can start at the beginning and reverse and end up just returningret.next
Can be
- And then define a
pre
The pointer starts pointingret
And move backwards in turn to find the area to be reversedPrevious node
, i.e.,1 nodes
And then operate hisNext node
Region reversal
-
If the pre pointer points to the 2 nodes to be reversed, the region will turn into 4->3->2->5 after the inversion. At this point, the next of node 1 still points to 2 nodes, and the final result will turn into 1->2->5. What we need, however, is for next of node 1 to point to 4->3->2->5
-
The operation is performed at the position of 2 nodes, and the reverse step is similar to the previous one, except that a variable needs to be added to receive the reverse result, which also points to 2 nodes at the beginning
- Invert the variable after the end
next
Point to the next one in the inversion regionNode 5
- And then finally reverse this one
Head node p
Return to join the original linked list - Overall animation presentation
Code implementation
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}* /
var reverseBetween = function (head, left, right) {
var ret = new ListNode(null, head)
var cnt = right - left + 1 // The number of ranges to reverse
var pre = ret
while (--left) {
pre = pre.next
}
pre.next = reverse(pre.next, cnt) If you reverse p directly, the first element of p still points to p, and the middle part of the inversion is skipped
return ret.next
};
function reverse(head, cnt) {
var p = null,
q = ret = head
while (cnt--) {
head = head.next
q.next = p
p = q
q = head
}
ret.next = q // The original head node is already pointing to NULL, and the next element after the inversion is connected
return p
}
Copy the code
Difficult problems can be solved easily
25. Flip linked lists in groups of K
Analysis of the
- If you don’t know how to reverse a linked list, this might make sense, but if you just get started, you might define a bunch of variables and end up getting tangled up, right
- in92. Reverse linked list IIIf the number of remaining nodes is smaller than the number to be reversed
k
Do not turn - I started off by defining one again
pre
The pointer starts pointinghead
- Let’s define a pointer
pre
At first pointret
At the end of each reversalk
After 10 nodes, move backwardk
Step until the end or the remaining number is less thank
- Eventually return
ret.next
Can be
Reference code
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
* @param {number} k
* @return {ListNode}* /
var reverseKGroup = function (head, k) {
if (k === 1) return head
var ret = new ListNode(0, head)
var pre = ret
while (1) {
pre.next = reverse(pre.next, k)
var n = k
while (n-- && pre) { // Go backwards after reversing
pre = pre.next
}
if(! pre)break // There is not enough time to get out of the loop
}
return ret.next
};
function reverse(head, k) {
var p = ret = q = head,
n = k
while (--n && p) {
p = p.next
}
if(! p)return head // The number of nodes to be reversed is less than k
p = null
while (k--) {
head = head.next
q.next = p
p = q
q = head
}
ret.next = q
return p
}
Copy the code
- If it’s not clear, you can draw it
— end —