Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to understand Java recursive single-linked list inversion". The content of the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to understand Java recursive single-linked list inversion".

First of all, we need to be clear about what recursion is. Recursion means calling yourself, right? For example, if there is a function f (n) = f (nMUI 1) * n, (note that I am giving an example here, this function does not give the end condition of recursion), assign n to 5, then:

-- > f (5)-- > 5 * f (4)-- > 5 * (4 * f (3)-- > 5 * (4 * (3 * f (2)-- > 5 * (4 * (2 * f (1)-- > 5 * (4 * (3 * (2 * 1)-- > 5 * (4 * (3 * (3 * 2))-- > 5 * (3 * (2 * 1))-- > 5 * (4 * (3 * 2))-- > 5 * 5 * (4 * 6)-- > 5 * 24-- > 120

After looking at the example, let's show code directly instead of BB:

/ * single linked list inversion-Recursive implementation * / public class ReverseSingleList {public static class Node {private int data; private Node next; public Node (int data, Node next) {this.data = data; this.next = next;} public int getData () {return data }} public static void main (String [] args) {/ / initialize the single linked list Node node5 = new Node (5 Node node4 null); Node node4 = new Node (4 # Node5); Node node3 = new Node (3 # Node4); Node node2 = new Node (2 # Node3); Node node1 = new Node (1 # Node2) / / call the inversion method Node recursiveList = recursiveList (node1); System.out.println (recursiveList) } / * Recursive implementation of single linked list inversion * @ param list is the incoming single linked list * / public static Node recursiveList (Node list) {/ / if the linked list is empty or there is only one node in the linked list, directly return / / is also the condition for recursive end if (list = = null | | list.next = = null) return list Node recursive = recursiveList (list.next); / / point the list.next.next pointer to the current linked list list list.next.next = list; / / point the list.next pointer to null list.next = null; / / return the inverted linked list recursive return recursive;}}

After the above code, you should be able to see that the core code is to recursively implement the reverse part of the single linked list of the five lines of code, do not underestimate these five lines of code, it is really not easy to figure it out.

I post these five lines of code here, and we analyze them line by line, trying to understand it after reading this blog. (I removed the comments, let's concentrate on these core lines of code)

If (list = = null | | list.next = = null) return list; Node recursive = recursiveList (list.next); list.next.next = list; list.next = null; return recursive

The first line is a judgment, if the conditions are not met, then go down. The second line is to call yourself, and the program goes back to the first line. If you do not meet the conditions, you will call yourself.

Just cycle until the conditions are met, so when will the conditions be met? That is, when list = = null or list.next = = null, take a look at the linked list defined by yourself is 1-> 2-> 3-> 4-> 5-> null, so when the condition is met, the linked list is 5-> null. After meeting the condition, the program continues to execute downwards, and after executing this line of code, let's take a look at the program execution result at this time:

I'll draw the above one (A Fan's painter is not bad, don't care about its beauty and ugliness)

Next, the program should execute list.next.next = list. After the execution, the linked list looks something like this:

That is the diagram, and the following is the result of the program breakpoint debugging program, which is found to be the same as the above figure:

The program continues to go down list.next = null, that is, point the next pointer of list to null:

You can see from the figure that list is 4-> null and recursive is 5-> 4-> null. Let's see if the result of the program is consistent with the figure:

It's exactly the same. No!

OK, remember the recursive function example we just started? Now that the execution is complete, let's start the execution next time, and let's move on to see that the linked list looks like this:

The next code that the program executes is four lines:

Node recursive = recursiveList (list.next); list.next.next = list; list.next = null; return recursive

To continue executing the program, let's look at the result. At the end of the run of list.next.next = list, the linked list is:

You can see from the figure that the linked list list is 3-> 4-> 3-> 4 loops, and the recursive is 5-> 4-> 3-> 3-> 3 loops. Let's see if the program is the same (here I truncated two loops as examples):

Next, the program executes list.next = null, and after execution, it points the next pointer of list to null:

You can see from the figure that list is 3-> null and recursive is 5-> 4-> 3-> null. See if the actual result is consistent with the analysis:

What does that mean?! It shows that our above analysis is correct. For the next program analysis, readers will study it by themselves. I believe that the following analysis will not be difficult for our smart readers.

Reverse the first N nodes of a single linked list

OK, let's strike while the iron is hot. We just reversed the whole single linked list through recursion. What if I just want to reverse the first N nodes?

For example, the single linked list is 1-> 2-> 3-> 4-> 5-> null. Now I just want to reverse the first three nodes to 3-> 2-> 1-> 4-> 5-> null.

Do you have any ideas?

When we reverse the entire single-linked list, it can be understood as passing a parameter n, which is the length of the single-linked list, and then the recursive program calls itself constantly, and then implements the entire single-linked list inversion. So, if I want to reverse the first N nodes, should I just pass a parameter n to solve it?

Let's just go to the code:

/ * * reverse the first n nodes of the single linked list * @ param list is the incoming single linked list, and n is the first n nodes to be reversed * / public static Node next; public static Node reverseListN (Node list,int n) {if (n = 1) {/ / when you want to reverse the linked list, save the node data after list to next next = list.next; return list } Node reverse = reverseListN (list.next, nmur1); list.next.next = list; / / points the pointer of list.next to the linked list list.next = next; return reverse;} that has not been reversed

Reverse part of a single linked list

Now that the entire single linked list is reversed and the first N nodes are reversed, what if there is a need to reverse some of the data? That's about it. The original linked list is 1-> 2-> 3-> 4-> 5-> null. Reverse part of it so that the reversed linked list is 1-> 4-> 3-> 2-> 5-> null.

To borrow the idea of inverting the first N nodes, should I pass in two parameters, one is the node that starts the reversal, the other is the node that ends the reversal, and then the recursive operation is OK?

Look at how the code is written:

/ * * reverse partial single linked list * @ param list is the incoming single linked list, m is the node that starts the reversal, and n is the reverse node of the end * / public static Node reverseBetween (Node list, int m, int n) {if (m = = 1) {return reverseListN (list,n);} list.next = reverseBetween (list.next,m-1,n-1); return list } Thank you for your reading, the above is the content of "how to understand Java recursive single-linked list inversion". After the study of this article, I believe you have a deeper understanding of how to understand Java recursive single-linked list inversion, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.