- 2021-04-08 00:52
*views 3*- data structure
- Linked list
- leetcode
- algorithm

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

- Python146 blogs
- Java131 blogs
- Vue86 blogs
- Flow Chart79 blogs
- javascript42 blogs
- C++41 blogs
- programing language38 blogs
- MySQL37 blogs
- more...

Daily Recommendation

©2020-2021 ioDraw All rights reserved

cartoon ： What is? JVM Garbage collection in China ? Huawei Hongmeng system HarmonyOS Learning 9 ： Hongmeng HarmonyOS History and future python Implementation in Mysql Data rollback rollback() And principle analysis The problem of string left rotation android 10.0 Version integration GMS package mysql actual combat 45 speak --- 33 Query large amount of data , Will the memory burst ajax send out post/get data ,java How to receive in the background RocketMQ Multiple namesrv Use of pits encountered 2021 Blue Bridge Cup B group C/C++ Personal records Blockchain journey ( three ) Smart contract and consensus mechanism