How to use Recursive and iterative methods to realize linked list inversion in python

This article mainly explains "how to use recursion and iterative methods to achieve linked list inversion in python". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to use recursive and iterative methods to achieve linked list inversion in python".

Define the linked list node structure:

Class ListNode: def _ _ init__ (self,data): self.data = data self.next = None

Convert L to a linked list:

Def make_list (L):

Initialize L to a linked list:

Head = ListNode (L [0]) cur = head for i in L [1:]: cur.next = ListNode (I) cur = cur.next return head

Traverse the linked list:

Def print_list (head): cur = head while cur! = None: print (cur.data,end='') cur = cur.next

Recursion reverses the linked list:

Def reverse_list (head):

Three elements:

1. Clear function function, which reverses the linked list and returns a header node

two。 End condition: returns when the linked list is empty or has only one node

If head==None or head.next==None: return head

3. Equivalent condition (narrowing the range). For arrays, the narrowing range is nMui-> nMel 1, while for linked lists, head-- can be considered.

> head.next reverse = reverse_list (head.next) # assume that reverse is an inverted linked list after head

The next thing to do is to connect the head node to the reverse that has been reversed:

Tmp = head.next tmp.next = head head.next = None return reverse # returns a new list

Iterative method:

Def reverse_list2 (head): # print_list (head) cur = head pre = None while cur: tmp = cur.next cur.next = pre pre = cur cur = tmp head = pre return head if _ _ name__ = ='_ main__': L = [3meme 2, 7, 8] head = make_list (L)

Positive sequence printing:

Print ('original list:') print_list (head) print ('\ n')

Print after reversal:

Revere = reverse_list (head) print ('inverted once list:') print_list (revere) print ('\ n')

Reverse 2:

Print ('head is') print_list (head) # finds that the head node becomes the last node at this time, indicating that the function is print ('\ n') # print ('revere is') # print_list (revere) # print ('\ n') print ('list:') print_list (reverse_list2 (revere)) that acts directly on the instance of head.

Thank you for reading, the above is the content of "how to use recursion and iterative methods to achieve linked list inversion in python". After the study of this article, I believe you have a deeper understanding of how to use recursive and iterative methods to achieve linked list inversion in python, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!