Shulou(Shulou.com)06/02 Report--

The main content of this article is to explain "what is the method of Python to achieve linked list inversion", interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "what is the method of Python to achieve linked list inversion"!

Using Python to reverse linked list

List inversion (while iterative implementation):

The inversion of the linked list introduces a cur_node variable to represent the current node; at the same time, it needs to introduce a variable new_link to represent the new linked list after inversion; and the intermediate variable tmp in the while loop is also needed to store the successor node of the current node to prevent the loss of the original linked list data.

Within the while loop (the loop condition is cur_node! = None, if set to cur_node.next, the last node cannot be reversed to the new linked list): first, the successor node of the current node needs to be passed to the intermediate variable tmp

The current node points to the new linked list new_link

When the current node points to the new linked list new_link, the new link header node is updated to the current node cur_node

Pass the intermediate variable tmp to cur_node to start a new cycle

Return new_link when the loop is over

Class Node (object): def _ _ init__ (self, value=None) Next=None): self.value = value self.next = next @ staticmethod def reverse (head): cur_node = head # current node new_link = None # indicates the reversed linked list while cur_node! = None: tmp = cur_node.next # cur_node subsequent nodes pass to the intermediate variable cur_node.next = new_link # cur_node points to new_link new_link = cur_node # reverse linked list update Cur_node is the new header node cur_node = tmp # the original linked list node moves back one bit return new_link link = Node (1, Node (2, Node (3, Node (4, Node (5, Node (6, Node (7, Node (8, Node (9) root = Node.reverse (link) while root: print (root.value) root = root.next

Running result:

Recursive implementation:

Recursive implementation is different from while implementation in that recursive implementation first finds the header node of the new linked list, and then returns the recursive stack, reversing layer by layer.

First find the header node of the new linked list (that is, traverse to the last node of the original linked list and return the last node)

Execute the subsequent code of the function body to point the tail node in the original linked list to the front node of the original tail node

The pointer to the front node points to None (to prevent an endless loop)

Return the header node of the new linked list to the function above, and repeat the above operation

Def reverse2 (head): if head.next = = None: # baseline condition for recursive stop return head new_head = reverse2 (head.next) head.next.next = head # the subsequent node of the head node of the current layer function points to the current head node head.next = None # the current head node points to None return new_head here, I believe you have a better understanding of "what is the method of Python to reverse the linked list" You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.