Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

preface

Algorithm has always been an important point to test the programming ideas of programmers. Generally speaking, small and medium-sized companies will not specifically ask this question in the interview. They usually ask questions based on the answers of the interviewer, for example, Glide will ask LRUCache,HashMap will ask the algorithm to store and calculate Hash. Recently I have also looked at some topics of LeetCode, to explain their own ideas

Code

First, let's define the entity class

public class ListNode { int val = 0; ListNode next; public ListNode(int data) { val = data; }}Copy the code

Then create a linked list

public static void main(String[] args) { ArrayList<ListNode> listNodeList = new ArrayList(); for (int i = 0; i < 5; i++) { ListNode listNode = new ListNode(i); listNodeList.add(listNode); if (i ! = 0 ) { listNodeList.get(i - 1).next = listNode; } } for (ListNode listNode : listNodeList ) { try { System.out.println(listNode.toString()); } catch (Exception e) { System.out.println(e.toString()); }}}Copy the code

Don't worry about the details, as long as we get what we want, right, baby

Then there's the reverse detail

public static ListNode rever(ListNode head) {
    if (head.next == null) {
        return head;
    }
    ListNode rever = rever(head.next);
    head.next.next = head;
    head.next = null;
    return rever;
}
Copy the code

Before to see an article number WeChat public say they don't plug in recursion, a few people head pressure stack, I think should not say so, even if the data is infinite and we should have been pressed a few methods in mind, the whole process and details of simple form an impression, below I use drawing to explain my train of thought

By the way, one of the properties of recursion is backtracking

For example, our first rever method passes the first data in the collection. That is, its base val is 0, and next’s ListNode val is 1. The following figure

Don't look too far back, just focus on what I've highlighted in blue, and you just have to remember that's all I'm passing around right now

if (head.next == null) {
    return head;
}
Copy the code

Because the property of a linked list is a node linked to another node, the above code is to determine whether the current node has a next node, no direct return, this is a recursion exit, do not set infinite recursion directly error

ListNode rever = rever(head.next);
Copy the code

The starting point of the recursion calls itself again with the argument next of head that we passed in at the beginning.

The val of the ListNode we passed initially was 0, and the val of the next ListNode must be 1. That’s what I highlighted in blue above. So the argument to ListNode is val = 1.

Once we get to this point, we’ll enter the new method, where rever’s head has val 1 and next points to a ListNode with val 2.

Check again to see if next is null for the parameter passed in. If not, continue down and go to

ListNode rever = rever(head.next);
Copy the code

Rever head: val = 2; next: ListNode: null I’m going to press three stacks here, and if I press any more, my head will smoke, and you’ll get more and more confused.

Return head, that is, return the current parameter to the past.

The point!!!!!! At this point the recursive exit has been triggered and the backtracking begins, so I will now simply write the stack we pressed below

The first stack

Public static ListNode rever(ListNode head) {if (head.next == null) { return head; } ListNode rever = rever(head.next); head.next.next = head; head.next = null; return rever; }Copy the code

The second stack

Public static ListNode rever(ListNode head) {if (head.next == null) { return head; } ListNode rever = rever(head.next); head.next.next = head; head.next = null; return rever; }Copy the code

The third stack

Public static ListNode rever(ListNode head) {if (head.next == null) { return head; } ListNode rever = rever(head.next); head.next.next = head; head.next = null; return rever; }Copy the code

I'll just press three, just to understand the flow

The next of head, the third stack argument, points to a ListNode that is null, so it goes straight back to the second stack. Because of recursive backtracking, calling your method back then is like building blocks

The third stack doesn’t meet the requirements, so we just return, so we consume this method, so we need to go back to the second stack. Notice this row right here

ListNode rever = rever(head.next);
Copy the code

At this point, we have reached our second stack, head val = 1,next refers to the ListNode val = 2, so we return the next data we passed :val = 2,next = null

And then continue down

head.next.next = head;
head.next = null;
return rever;
Copy the code

Val = 2,next = null

After the first line of the code above, our ListNode changes: val = 2,next = head

And now the data looks something like this

But we don’t want a two-way list, so we do the second row

head.next = null;
Copy the code

And then the data looks like this

A: wow! You’ve successfully reversed a node, and now we’re looking at the third row

return rever;
Copy the code

This sentence returns our reversed data and represents the death of the second stack.

Val = 1,next = null; val = 1,next = null;

Let’s move on to the code

ListNode rever = rever(head.next);
head.next.next = head;
head.next = null;
return rever;
Copy the code

The current rever data is what I just said, so let’s go to the second row.

head.next.next = head;
Copy the code

Remember, this is the first stack, and we said that val = 0 on the first stack, val = 1 on the next stack, because of the inversion on the second stack, it now points to null on the ListNode;

Head. Next equals the following

Head. Next. Next is equal to this

In other words, turn this null back into our first data

And then the old way — it doesn’t work both ways, baby. Empty him out

head.next = null;
Copy the code

then

return rever;
Copy the code

Wow, that’s the end of a three-node list. Let’s print it

Ok, so that's how I think about recursively reversed lists. Some people might be confused when they first read them. Oh, my God, head.next-next, what the hell, don't worry

Well, THAT’s all. I’ve got a headache and I’ve gone to sleep. Tomorrow I’ve got a lot of work to do