- 2021-04-08 00:52
*views 7*- 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

- Python153 blogs
- Java136 blogs
- Vue88 blogs
- Flow Chart79 blogs
- javascript44 blogs
- C++43 blogs
- MySQL39 blogs
- programing language39 blogs
- more...

Daily Recommendation

©2020-2021 ioDraw All rights reserved

unity3d Realize the first person shooting game CS Counter Strike （ one ）（ First person movement ） Those big black technology visual screens , How did you do it ? Template direct application Six years Java Programmer turns to duck HTML+CSS+JS Realized games -" scissors "MySQL— Relational database macOS Big Sur The installation could not be completed Big Sur Why can't I install it ? Unexpected Python Cherry tree （turtle Gorgeous style of Library ）element-ui in collapse Default deployment python Read from the specified directory Excel Table all sheet Data “Python Is the best language in the world ”