About this problem , In general, there are two types of methods ： Iteration and recursion .
Let's start with iteration , The idea of recursion should be extended on iteration .
common

<> Three finger needling

thinking
Use one cur Pointer to locate the position of the node currently traversed .
One pre Pointer to record the position of the previous node , In order to reverse the direction of the current node .
Use a pointer last To save the location of the next node , It can ensure that the pointer of the current node turns back , You can continue to traverse .
Such a traversal is enough to complete the inversion , Only three pointer spaces are created . Time complexity O（n）, Spatial complexity O（1）.
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* pre =
NULL, * cur = head; struct ListNode* last; while (cur != NULL) { last = cur->
next; cur->next = pre; pre = cur; cur = last; } return pre; }

So move it one by one cur get to NULL Time , End of cycle , And ,pre Has also moved to the previous position , that is

cur And last All point to NULL.pre It becomes the head node （ It's not a sentry post ） return .

meanwhile , Also when head->next== NULL Or this head==NULL Time , That is, when the linked list has only one node or is empty , The same is true .

The linked list is empty , There's no circulation at all , Direct return pre Null pointer .

When a Nordic list has only one node , It will only cycle once ,cur point NULL, and pre Point to the node .

Using the method of linking and inserting in linked list .

If all nodes are inserted by the head method , Form a linked list , The final print will be entered in sequence , Reverse order printing .

That is to use this property , Modify the linked list , reversal .（ I see this is really exclamation algorithm is too strong ）. There's no need to open up space .

Because the linked list cannot be accessed randomly , You can only traverse each node in turn , So take advantage of that .
It can be considered , Every node traversed , The node can be regarded as the head node .

about 1, To satisfy the problem , then is 5->4->3->2->1->NULL

To extend the linked list by supposing to insert the head first
Open up space in turn , At the same time, it is set as the head node , The pointer of the new space to be opened up points to the head node .
According to this algorithm , Operation on linked list .

First of all phead Pointer to NULL, Because the first node is brought into the loop , This is not the first special node , It is equivalent to a node in the middle , The new node should point to the head node , Only in this way can the head insertion method be satisfied . And at the end of the cycle , At the end of the list is a NULL.

To sum up ,
A pointer points to a node in turn , All the nodes must satisfy the requirements ,cur->next Point to head node .
At the beginning of the next cycle , The node should be the head node , such , To be satisfied , The linked list just reverses the direction of the pointer .
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* phead =
NULL; struct ListNode* cur = head; while (cur) { struct ListNode* la = cur->next
; cur->next = phead; phead = cur; cur = la; } return phead; }

Every time in accordance with the original list to traverse the time , Make sure you can cur The pointer points to the next node in turn . Use a pointer to report the location of the next node . After setting the head node ,cur We need to extract the next node （ It is equivalent to adding nodes when creating linked list with head insertion method ）.
This method is quite fast

<> recursion

Recursion has always been a headache and brain dead method .
To sum up , Three conditions for recursion ：

* It can turn a problem into a new one , The solution of the new problem and the original problem should be the same or similar , What's different is just the object being processed , And these objects should gradually become smaller and change regularly .
* Through the above continuous transformation, the problems can be simplified into simple and similar problems .
* There must be a recursive exit or boundary
（ The limit of taowa ）

recursion “ Divide and conquer ”
void p( Parameter table ) { if( Recursion end condition / Recursive exit ) Direct solution // Recursive termination condition else p( Smaller parameters )// Recursive entry , step
Simplify a big problem into a finite number of small problems to solve one by one

First think about how to deal with a linked list with only one node

Then don't deal with it cur->next point NULL Node of , Direct return .

What if it's a linked list with only two nodes ?

head The node is 1, And then you have to 1 Points to the node 2 Of next Point to node 1, And then you have to 1 Nodal next point NULL. about 2 Nodes are not processed , But I want to go back 2 Location of node , Is the new head node .
that 3 individual ,4 individual ,5 individual … What about the linked list of nodes ?

This is a doll . Set each cur It's all head pointers , Which node does each pair go to , The nodes are all head pointers .

Recursion starts with the first pointer , Until a node's next point NULL. Return to the previous recursive node . There is no operation on the last node , At the same time, it also returns the address of the last node .
Each head pointer and the following node can be regarded as a pattern of two nodes , Only the next node is inverted .
This is similar to the iterative head insertion method , Reverse pointer operation is only performed on two nodes . Each recursion is to find the next head node .

The end of each recursion , It's all about this head And the next node , These two nodes reverse the pointer .
No matter how many linked list nodes there are , I can convert it into a linked list of two nodes by recursion , And reverse it .