This is my first blog post. I participated in the creation activity of gold diggers and started my writing path together.

Related to LeetCode topics: 206. Reverse linked lists, 25. (Reverse is both used in English, why is one Chinese translation “reverse” and the other “turn”?)

The ListNode class ListNode has been defined. The class members have val and a next variable (pointer) to the next node.

Reverse a linked list

Please skip to LeetCode to read the complete topic description. The numbers in the figure can be considered as val values for each node.

The iteration

Reverse the linked list problem, the solution that usually comes to mind quickly is iteration, using while with prev, cur pointer for linear iteration to modify the next pointing of each node. It’s not the point of this article.

function reverse(head) { if (! head) return head; let prev = null, cur = head; while (cur) { const next = cur.next; cur.next = prev; prev = cur; cur = next; } return cur; }Copy the code

recursive

What I find difficult to understand is the use of recursion to solve problems. Yes, it’s the Matryoshka doll in the title! More on that later.

A crude understanding of recursion, where a function is executing and then calling itself internally, breaks up a big problem into multiple identical sub-problems. When writing a recursive function, there are three main points to determine: ** input parameters, exit conditions for calling the function itself, and ** output parameters.

Given that the current node is pointed to by a cur variable, in an inverted linked list,

  • To move the cur pointer along the list, the recursive entry is the next node of the current node, cur.next;
  • Exit condition: the current node cannot recurse downward if there are no subsequent nodes, i.e. the function itself will not be called if cur.next does not exist.
  • What are the exit parameters? The ultimate goal of our whole function is to return the head node of the reversed list, which is the last node of the original list (denoted as last). The last node is returned at the exit condition step, and it is also returned at the recursion level above it, that is, each recursion level directly returns the result of its own internal function execution.

So now I have a function,

function reverse(node) { let cur = node; if (! cur.next) return cur; const last = reverse(cur.next); // line a return last; }Copy the code

The next step is to resolve the reverse action, where the node’s next pointer points to the previous node.

In the current function, there is a node pointing to cur. How do I get the last node? As a single linked list node, it looks like you can’t get the previous node, but you can get the subsequent nodes. Its next node is cur.next, and we can reverse that node so that its next points to the current node cur. Available code: cur.next. Next = cur;

Then a new question arises, which line should I put this line of code on?

Recursive execution is the same as taking apart a fully nested Matryoshka doll.

(P.S. wanted to give an example of the popular onion model, but realized the metaphor was flawed. Who uncovers an onion layer by layer and then wraps it up again?) (P.S. was proud of himself for coming up with the doll metaphor, but a search engine revealed that a bunch of their predecessors had already done it, crying. But not on the Nuggets? Laugh.)

A baby is divided into two parts of the upper and lower body, assuming that only one part can be taken at a time. You start with the top of the outermost part, then the second largest part… Down to the smallest upper body, and then there’s the smallest undetachable baby at the bottom, which is like that little piece of code that exits the recursive logic. Then start taking the smallest lower half, the second smallest lower half… Finally, the largest lower body.

Going back to the semi-finished code block above, demarcated by the comment “line α,” the top half of which is the top half of the doll, all of the code below line α (including the reverse(cur.next) line) is executed during recursion.

Returning to the question of which line the code to modify the pointer is placed on, the question becomes whether the code should be inserted above or below line α.

This comes out of the simulation hypothesis. If the code is placed above line α and executed from the beginning, nodes 1 and 2 will refer to each other, forming an infinite loop, which is equivalent to constantly taking and removing the upper halves of the outermost two nesting dolls.

STEP1:1 (cur) – > 2 – >… = > STEP2:1 < – > 2 (cur)…

So you can only put it under row alpha.

The current code is updated to:

function reverse(node) { let cur = node; if (! cur.next) return cur; const last = reverse(cur.next); // line a cur.next. Next = cur; return last; }Copy the code

We then execute the function completely from the beginning, passing in the head node (val is 1) as an argument. Analogous to disassembling a Matryoshka doll, start from the outside in and keep taking the upper part of the body (execute the upper half of the code), imagining some key points:

  • What happens to the linked list when you take the innermost layer of the smallest indivisible child?

The code completes the first half of the recursion and exits the recursive logic at the point where the cur variable (pointer) points to the last node and is about to return it.

1 – > 2 – > 3 – > 4 – > 5 (cur) – > null

  • What happens to the first lower half of the linked list?

At this point, the call stack first executes to the bottom half of the code, and the last variable is assigned to the node returned by the smallest undetachable child, that is, val is 5, and cur points to the node with val is 4. After executing cur.next-next = cur,

1 – > 2 – > 3-4 (cur) < – > > (last) x 5 null

This is followed by successive layers of the lower body being removed from the inside out.

1 – > 2 – > 3 (cur) < < – > 4-5 (last)

1 – > 2 (cur) < – > 3 < – < 4-5 (last)

1 (cur) < < < — – > 2-3-4 < – 5 (last)

Finally, when we get to the lower half of the maximum, cur is the node with val 1, but we find that its next is not modified, causing the linked list to be referenced repeatedly. At this point we expect cur.next = null; Is it necessary to add a condition that the code must be the original header to execute it? It turns out that by doing the deductive implementation, it’s not necessary.

According to the LeetCode test case set, which often has empty nodes, the code also needs to add a judgment processing for empty nodes. So the final code looks something like this:

function reverse(node) { let cur = node; if (! cur || ! cur.next) return cur; const last = reverse(cur.next); cur.next.next = cur; cur.next = null; return last; }Copy the code

Russian nesting doll summary

To write a recursive function, we must determine the entry parameters, exit parameters, and exit recursion conditions according to the ultimate goal.

The execution of the whole code is divided into two parts, the demarcation point is to call the execution function itself that code statement. All of the upper half of the execution will start to execute the lower half, so the most inner layer of the smallest indivisible child (hereafter referred to as “the smallest child”) and the first minimum lower half is the key (that is, the first time to exit the recursive condition and the second half of the execution), when writing code can take them as a breakthrough point.

Flip linked lists in groups of K

And then we try to solve K pairs of flipped lists using Matryoshka dolls. See the link for a description of the topic.

For example, when k=2,

K = 3,

The first step is to determine the three elements of the recursive function according to the objective.

Taking k=2 as an example, the input parameter is the original head node 1 and 3 of each group, and the output parameter is the new head node 2 and 4 of each group. Exit recursion condition – if the number of nodes in this group is less than k, the original head of the group is returned.

Function reverseK(head, k) { / /... const newHead = reverseK(? , k); // How to pass in the header of each subsequent group? return newHead; } // ----------------------------------------------------------------------------- // WIP 2 function reverseK(head, k) { let end = head; for (let i = 1; i < k; i++) { if (! end.next) return head; End = end.next; } const newHead = reverseK(end.next, k); return newHead; }Copy the code

Then consider how to reverse each set of nodes.

The nesting operation is fast-forward to the step of taking the smallest baby, that is, the exit recursion condition is entered, and the head node of the last group (the node with val 5) is returned. The next step is to take the minimum lower half, (see the code block annotated as “WIP 2”). In this context, newHead is node 5, head is 3, and end is 4. To begin the reversal, we will change 3 — >4 to 3< — 4.

Given the beginning and end of the node, it should not be a problem to write an inversion, as in the beginning of this article, using the prev, cur pointer +while iteration to change the cur next pointer. In order to reuse it, let’s separate it out here into separate functions.

Function reverse(head, end) {// Let prev = null, cur = head; const endNext = end.next; // To reverse the end, use end.next to judge while (cur! == endNext) { const next = cur.next; cur.next = prev; // In connection with the current calling context, the first time through the loop, cur is 3, and its next is changed to point to null prev = cur; cur = next; } return prev = 4; cur = 5; }Copy the code

Reverse (3, 4) returns a prev pointer to the head node 4, and the current set of lists changes to: 4 – >3 – > NULL

The next question to consider is whether the call to the inverted function should be placed above or below the recursive function. I’m going to conclude this by assuming and deducting, up and down. Let’s put it down here. The code is updated as follows,

WIP 3 function reverseK(head, k) {// const newHead = reverseK(end.next, k); const realNewHead = reverse(head, end); return newHead; }Copy the code

It turns out that reverse actually returned the new head node, and reverseK actually returned the previous head node. Let’s fix the code,

// WIP 4 function reverseK(head, k) { let end = head; for (let i = 1; i < k; i++) { if (! end.next) return head; end = end.next; } const lastHead = reverseK(end.next, k); const newHead = reverse(head, end); return newHead; }Copy the code

The next step is to connect the current new tail node to the previous head node. In the current context, make node 3’s next point to 5. How do I get 3? It’s the original head node, and the variable head is still pointing to it. That translates to code: head. Next = lastHead;

At this point, the logic is pretty much connected. Finally, according to the convention, fill in the judgment of the empty.

Final code, done!!

function reverseK(head, k) { if (! head) return head; let end = head; for (let i = 1; i < k; i++) { if (! end.next) return head; end = end.next; } const lastHead = reverseK(end.next, k); const newHead = reverse(head, end); head.next = lastHead; return newHead; } function reverse(head, end) { let prev = null, cur = head; const endNext = end.next; while (cur ! == endNext) { const next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; }Copy the code

Next, you can try to solve LeetCode 24 using the same idea above. Swap nodes in a linked list in pairs.

conclusion

The essence of the two questions in this paper is solved by recursion. In the process of solving them, I tried to explain my thinking steps step by step, and described the recursion behavior with the help of the doll metaphor. Hopefully this article will help you understand recursion better. If there is anything wrong with the article or code, please correct it. Thank you for your attention.