The question of reverse linked list is really a favorite question for interview. It looks simple, but it is not easy to use two methods to go through the bug free. A large number of people can be screened out during the interview, and they are very interested in the interview of junior and senior.

Today, Qi sister will take you to comb clear thinking, thinking clearly to write code such as god.

The title


This is from likou Chinese station cut down, but this output is not very image.

To reverse the list, you don’t actually flip it over, you just move the next pointer.

What does that mean?

Let’s start by inverting the array.

An array is a physically contiguous data structure that is inverted to place a 1 instead of a 5.


But a list is not. Because a list is physically discontinuous, its cells are connected by a next pointer, and each ListNode is not necessarily next to each other in memory.

So if you reverse a list, you don’t have to put a 5 in place of a 1, just because they want to be.

So how do you guarantee this order?

  • That’s the next pointer.

Following the direction of the next pointer is the order of the list. This ensures that once we get the head node, we control the entire LinkedList.

So for the example in the question, the graphic point looks like this:


So the element doesn’t move, it just moves the little pointer, and it reverses.

The recursive method

Do you remember the three steps of recursion?

Base case + disassemble + combination

Do not remember quickly in the public number to reply to the “recursion” two words, to get a detailed explanation of the introduction of recursion.

So let’s look at this:

base case:

When there is only one node, or there are no nodes, which is

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

Actually, strictly speaking, when there is only one node, it is not a base case, but a corner case.

It could have broken down to node == null, but could not have been omitted because of the dereference operation on Node.next.

Apart:

Recursive disassembly is the decomposition of the big problem into smaller problems until the base case can be returned to the third step of the combination.

So this is


Combination:

Combinatorial means, assuming we can get a solution to a small problem, then use the solution to a small problem to construct a solution to a big problem.

So how do we construct it in this problem?


It’s pretty obvious here, you can just put a 1 after a 2, but how do you get a 2?

Remember, in the original problem, 1 also points to 2

Next = node2,

Then point 2 to 1: node2.next = node1

Node1.next-next = node1

Clear thinking is not around, look at feel around is not clear hum ~

code

The recursive code is neat to write:

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
 ListNode newHead = reverseList(head.next);  head.next.next = head;  head.next = null;  return newHead;  } } Copy the code

Time complexity

As we said in recursion, the method of time complexity analysis for recursion is to draw a recursion tree and add up The Times of each node.


So this recursion tree is a very simple list of single chains, and what each node does is those three lines of code, which is what the combination does, which is order 1 time, so there are n nodes, so the total time is order n.

Spatial complexity

So it’s pretty obvious from the recursion tree, each level is just a little bit of a variable, order one, so the total space is order n.

Iterative solution methods

Who can tell me this professional Chinese saying?

The Iterative approach is to run the Linked List over, pointing the next pointer to the previous node until it is complete.

It’s too abstract, even in an interview.


That is, flip the next pointer of 1 over to NULL; Flip the next pointer of 2 over to point to 1; Flip the next pointer of 3 to 2; .

So we also need a variable to record the previous node of the current node. Let’s set it to prev.

Also, as soon as we flip the pointer over, the node behind it is lost. Therefore, an additional variable is required to record the following node, set to NXT, so that we do not lose ~

Step1.

Flip arrow: Set 1’s next pointer to NULL;



In this case, we also make it clear that the prev initialization should be NULL.

Then move all three variables to the next position:


Step2.

Flip arrow: Turn 2’s next pointer to 1,


Then a threesome:


Step3.

Flip arrow: Move 3’s next pointer to 2,


To march again:


Step4.

And reverse 4:


Go further back:


Step5.

Invert next of 5:


But because our while loop contains

“Flip Arrow” + “Threesome”

Two steps, so there’s still one last threesome to go, to become:


The end condition of the while loop is very simple. Just draw a picture.

When curr = null, prev is returned.

Ok, look at the code:

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

 while(curr ! =null) {  ListNode nxt = curr.next;  curr.next = prev; // Flip the arrow  prev = curr; / / company  curr = nxt; / / company  }   return prev;  } } Copy the code

Time complexity

The time complexity here is pretty obvious, just going through the list, so it’s order n.

Spatial complexity

Space is O (1).