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 .
<> Head insertion
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 .
struct ListNode* reverseList(struct ListNode* head) { if(head==NULL||head->next
==NULL)// Make sure head Not empty again head->next End recursion and return head Valid address of return head; struct ListNode*
phead=reverseList(head->next); head->next->next=head; head->next=NULL; return
phead; }
This problem deepens my understanding of recursion and linked list , I hope everyone can have a deeper understanding of recursion and linked list .
Thank you for watching .
Technology