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

This article focuses on "how to achieve Java single-linked list inversion", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "how to achieve Java single linked list inversion"!

Background review

The storage structure of the single linked list is shown in the figure:

The data domain stores data elements, and the address of the successor node in the pointer domain.

Let's take a single linked list pointing to N1-> N2-> N3-> N4 as an example:

The inverted linked list points to the figure:

We define the following node classes in the code to make it easier to run the test:

/ * * Node class * (because it is run later in the main method, for convenience definition as static inner class) * / static class Node {int val; / / data field Node next; / / pointer domain, pointing to the next node Node (int x, Node nextNode) {val = x; next = nextNode;}} to reverse the linked list through loop traversal

The realization idea: starting from the chain header node, cycle through each node in turn, and change the corresponding pointer domain of the node to point to the previous node.

The code is as follows:

/ * Loop traversal method to reverse the linked list * @ return * / public static Node cycleNode (Node head) {Node prev = null; / / save the information of the previous node / / cycle through the node while (head.next! = null) {/ / 1 in the linked list. First save the information of the next node of the current node to tempNext Node tempNext = head.next; / / 2. Modify the pointer domain of the current node to point to the previous node (if it is the first time to enter the loop head node, the last node is null) head.next = prev; / / 3. Save the current node information to prev (as the "previous node" used in the second step of the next loop) prev = head; / / 4. The pointer domain of the current node has been modified in the previous 123step. Let head repoint to the next node to be processed, head = tempNext. } / / after the above cycle is completed, only the node direction between the header node and the penultimate node in the original linked list is actually modified, and the penultimate node (tail node) is not processed / / at this time, prev points to the penultimate node in the original list, and head points to the pointer domain of the tail node / / processing tail node to point to the previous node head.next = prev / / return the tail node, which is not only the tail node in the original linked list, but also the head node in the reversed new linked list return head;}

Test results:

Public static void main (String [] args) {/ / construct test cases with linked lists pointing to N1-> N2-> N3-> N4 Node N4 = new Node (4, null); Node n3 = new Node (3, n4); Node N2 = new Node (2, N2); Node N1 = new Node (1, N2); Node head = N1; / / output test case System.out.println ("original list points to:"); printNode (head) / / reverse linked list System.out.println in normal way ("Circular reverse linked list points to:"); head = cycleNode (head); printNode (head);} / * * Circular print linked list data field * @ param head * / public static void printNode (Node head) {while (head! = null) {System.out.println (head.val); head = head.next;}}

As you can see, the linked list pointing to N1-> N2-> N3-> N4 has changed to N4-> N3-> N2-> N1 after running the inversion method.

Implement list inversion by recursion

Implementation idea: starting from the chain header node, recursively traverse each node in turn, and change the corresponding pointer domain of the node to point to the previous node (yes, the processing process in each recursion is the same as in the loop above)

Code implementation:

/ * Recursive implementation of linked list reversal * after the execution of the recursive method Head points from the original linked list order: head node-> the first node in the tail node (head node) to the inverted list order: tail node-> first node in the head node (tail node) * * @ param head head node * @ param prev stores the last node * / public static void recursionNode (Node head Node prev) {if (null = = head.next) {/ / set recursive termination condition / / when head.next is empty Indicates that it has been recursive to the tail node in the original linked list. At this time, the tail node pointer domain is processed separately, and then the recursive head.next = prev is ended. Return;} / / 1. First save the information of the next node of the current node to tempNext Node tempNext = head.next; / / 2. Modify the pointer domain of the current node to point to the previous node (if it is the first time to enter the recursive header node, the last node is null) head.next = prev; / / 3. Save the current node information to prev (as the "previous node" used in the second step of the next recursion) prev = head; / / 4. The modification of the pointer domain of the current node has been completed in the previous 123 steps, so let head repoint to the next node to be processed head = tempNext; / / recursively process the next node recursionNode (head, prev);}

Test results:

Public static void main (String [] args) {/ / construct test cases with linked lists pointing to N1-> N2-> N3-> N4 Node N4 = new Node (4, null); Node n3 = new Node (3, n4); Node N2 = new Node (2, N2); Node N1 = new Node (1, N2); Node head = N1; / / output test case System.out.println ("original list points to:"); printNode (head) / / Recursive reverse linked list System.out.println ("Recursive reverse linked list points to:"); recursionNode (head, null); printNode (head);} / * * Circular print linked list data field * @ param head * / public static void printNode (Node head) {while (head! = null) {System.out.println (head.val); head = head.next;}}

Note: in the above test code, an instance of the Node class head is passed as a parameter when the recursive function is called

According to the method call parameter passing in Java, the basic type is value passing, and the object type is reference passing. = >

Because the reference to the head object is passed when the recursive function is called, and we have changed the object pointed to by the head reference several times during the running of the recursive function

Then when the recursive function is executed, the object pointed to by the head reference is theoretically the tail node N4 in the original linked list, and the order of the linked list has become N4-> N3-> N2-> N1.

The final result of the program is quite different from what I imagined!

So what's the problem?

Recursive reverse linked list problem troubleshooting and extended problem location

Since the program doesn't work as expected, let's add comments to print the object address where the head object reference may change, and see if we can find out what the problem is:

The commented code is as follows:

Public static void main (String [] args) {/ / construct test cases with linked lists pointing to N1-> N2-> N3-> N4 Node N4 = new Node (4, null); Node n3 = new Node (3, n4); Node N2 = new Node (2, N2); Node N1 = new Node (1, N2); Node head = N1; / / output test case System.out.println ("original list points to:"); printNode (head) / / Recursive reverse linked list System.out.println ("Recursive reverse linked list points to:"); System.out.println ("head reference points to object before recursive call:" + head.toString ()); recursionNode (head, null); System.out.println ("head reference points to object after recursive call:" + head.toString ()); printNode (head) } / * print linked list data field * @ param head * / public static void printNode (Node head) {while (head! = null) {System.out.println (head.val); head = head.next }} / * * Recursive implementation of linked list reversal * after the execution of the recursive method Head points from the original linked list order: head node-> the first node in the tail node (head node) to the inverted list order: tail node-> first node in the head node (tail node) * * @ param head head node * @ param prev stores the last node * / public static void recursionNode (Node head Node prev) {System.out.println ("head reference points to object in Recursive call:" + head.toString ()) If (null = = head.next) {/ / set the recursive termination condition / / when the head.next is empty, the table name has been recursed to the tail node in the original linked list, then the tail node pointer domain is processed separately, and then the recursive head.next = prev; System.out.println ("the head reference points to the object before the recursive call is returned:" + head.toString ()); return;} / / 1. First save the information of the next node of the current node to tempNext Node tempNext = head.next; / / 2. Modify the pointer domain of the current node to point to the previous node (if it is the first time to enter the loop head node, the last node is null) head.next = prev; / / 3. Save the current node information to prev (as the "previous node" used in the second step of the next recursion) prev = head; / / 4. The modification of the pointer domain of the current node has been completed in the previous 123 steps, so let head repoint to the next node to be processed head = tempNext; / / recursively process the next node recursionNode (head, prev);}

Running result:

Judging from the above running results, the object pointed to by the head reference does change during the execution of the recursive function.

Notice the change of the head reference pointing to the object in these three places before / before / after the call returns:

You can find that although the object that the head reference points to does change during the execution of the recursive function, it is actually lonely!

After the function call returns, the object pointed to by the head reference is still the one before the call!

In debug mode, let's take a closer look at whether the head object before and after the recursive function call is exactly the same:

From the above two figures, we can see that although the object pointed to by the head reference before and after the recursive call is the same, the properties of the object itself (pointer domain) have changed!

This shows that the execution of the recursive function is not doing useless work, but actually changing the pointing order of the nodes of the original linked list!

It is only because after the execution of the recursive function, the incoming head object reference is not successfully directed to the header node N4 of the reversed new linked list.

At this time, the head object reference still points to N1 as before, and N1 becomes the tail node in the reversed new linked list. At this point, we have perfectly lost the reversed new linked list, and the head pointing to the tail node can not traverse to other nodes of the new linked list at all.

Problem extension: exploring the essence of parameter passing in Java method calls

From the location of the problem above, we can see that the problem lies in my misunderstanding of parameter passing in Java method calls, so let's explore the process of parameter passing in Java method calls in detail.

Shape participation parameter

Test the sample code:

Public static void recursionNode (Node headNode, Node prevNode) {/ / do something...} public static void main (String [] args) {/ / init head... RecursionNode (head, null); / / call method}

In the sample code above, we defined the recursionNode () method and called it in the main () method

The headNode prevNode in the method definition is the formal parameter, and the head null passed in when the call is called is the actual parameter

Value transfer

If the formal parameter types in the method definition are basic data types (byte, short, int, long, float, double, boolean, char), when the method is called, the argument-to-parameter transfer is actually a value transfer, passing a copy (copy) of the actual parameter value.

Therefore, arbitrarily modifying the value of the parameter in the body of the method will not affect the value of the parameter outside the method.

Reference transfer

If the formal parameter type in the method definition is an object type (an array with basic data types), the argument-to-parameter transfer is actually a value transfer when the method is called, passing the reference address of the argument object.

How do you understand the concept of the reference address of this argument object? Let's take a look at the memory model diagram of the sample code runtime (it simply abstracts the parts of stack and heap. If there is any error, you are welcome to correct it)

As shown in the figure, the main and recursionNode methods are actually stacked into the virtual machine stack of the current thread as different stack frames

The head reference in the main method actually holds an address through which you can find a Node object in the heap

The headNode reference in the recursionNode method actually holds an address through which you can find a Node object in the heap

So when the recursionNode method is called in the main method, what exactly is passed from the argument head to the parameter headNode?

Obviously, what is passed is the address that can be addressed to a Node object in the heap. )

Thus, the actual parameter head object reference and the formal parameter headNode object reference have the same address value, pointing to the same Node object in the heap.

Through either of these two references, you can change the properties and state of the corresponding object in the heap

What happens after a recursive method call

After understanding the essence of object reference transmission, looking back at the problem that the actual result is inconsistent with the expected result after the recursive method call above, everything is easily solved.

As shown in the figure, although the headNode reference in the recursive method recursionNode () method does point to the new Node object N4 after the recursive call, the head reference in the main method still points to the Node object N1 before the recursive method call (with the execution of the recursive method, the pointer field inside the N1 object has changed)

Correct recursive implementation of linked list reversal / * Recursive implementation of linked list reversal, after the execution of the recursive method Head changes from the starting point in the head node-> tail node (the head node) to the start point in the tail node-> head node (tail node) * * @ param head head node * @ param prev stores the last node * / public static Node recursionNode2 (Node head) Node prev) {if (null = = head.next) {/ / set recursive termination condition head.next = prev Return head;} Node tempNext = head.next; head.next = prev; prev = head; head = tempNext; Node result = recursionNode2 (head, prev); return result;}

Test results:

Public static void main (String [] args) {/ / construct a test case with a linked list pointing to N1-> N2-> N3-> N4 Node N4 = new Node (4, null); Node n3 = new Node (3, n4); Node N2 = new Node (2, N2); Node N1 = new Node (1, N2); Node head = N1 / / output test case System.out.println ("original linked list points to:"); printNode (head); / / New Recursive reverse linked list System.out.println ("New Recursive reverse linked list points to:"); head = recursionNode2 (head, null); printNode (head) } / * print linked list data field * @ param head * / public static void printNode (Node head) {while (head! = null) {System.out.println (head.val); head = head.next }} at this point, I believe you have a deeper understanding of "how to achieve Java single-linked list inversion". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.