Python data structure flipped linked list

Flip a linked list

Example: Given a linked list 1->2->3->null, the flipped linked list is 3- >2->1->null

A relatively simple method is to use the "extraction method". That is to first create a new empty node, then traverse the entire linked list, and make the traversed nodes point to the head node of the newly created linked list.

For example, the steps are as follows:

1. Create a new empty node: None
2. 1->None
3. 2->1->None
4. 3->2->1->None

The code is very simple:

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  temp = None 
  while head: 
   cur = head.next 
   head.next = temp 
   temp = head 
   head = cur 
  return temp 
  # write your code here

Of course, there is a slightly more difficult solution. We can write the code for in-place flipping of the nodes in the linked list by sequentially picking and linking them:

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  if head is None: 
   return head 
  dummy = ListNode(-1) 
  dummy.next = head 
  pre, cur = head, head.next 
  while cur: 
   temp = cur 
   # 把摘链的地方连起来 
   pre.next = cur.next 
   cur = pre.next 
   temp.next = dummy.next 
   dummy.next = temp 
  return dummy.next 
  # write your code here

It should be noted that when picking When chaining, don’t forget to connect the removed parts again

Thank you for reading, I hope it can help everyone, thank you everyone for supporting this site!

For more articles related to flipping linked lists of Python data structures, please pay attention to the PHP Chinese website!