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

Editor today to take you to understand what is the method of Python to judge palindromes linked list, the knowledge points in the article are introduced in great detail. Friends who feel helpful can browse the content of the article together with the editor, hoping to help more friends who want to solve this problem to find the answer to the problem. Follow the editor to learn more about "what is the method of Python judging palindromes linked list".

What is palindromes?

To put it simply, the number of palindromes is the same when you read it backwards, for example, 12321, 1221, 1111, etc., 12321 for positive reading and 12321 for backwards reading.

First, receive a list of user input numbers and convert it into a linked list

For example, user input: 1 2 3 2 1, converted to a linked list, as shown in the following figure

First receive a list of user input numbers, each separated by spaces, truncate the string with split, use map, map each element to an int type, then convert it to list, and use a loop to take out each element and add it to the linked list.

Lt = list (map (int, s.split (')

The code is as follows:

# linked list class class ListNode: def _ _ init__ (self, x): self.val = x self.next = None # string converted to linked list def list_node (s): lt = list (map (int) S.split ('')) l = ListNode (0) # create a linked list with header node 0 p = l for i in range (len (lt)): p.next = ListNode (lt [I]) p = p.next return l.next to determine whether it is a palindrome or not

Use the fast and slow pointer method to find the middle position, the slow pointer jumps one grid at a time, and the fast pointer jumps 2 squares at a time, so the fast pointer is twice as much as the slow pointer. When the fast pointer is None, it means that the linked list ends, that is, when the fast.next.next=None in the code, the linked list ends. At this time, the slow pointer just points to the middle position of the linked list, so you get 3 is the middle position, from the next position of 3. Then the linked list at the beginning of the next node in the middle position is flashback, that is, 21, and 12 after flashback.

Whether it is equal to the linked list in front of the middle position. If p==None indicates that the linked list is None, the direct return True,p==None,q must also be None (see the flashback method below)

While p is not None and q is not None: if p.val is not q.val: return False q, p = q.next, p.next

Complete code:

# is palindrome def palindrome (l): if l is None: return True slow = fast = l # find the intermediate node, one fast and one slow pointer, the fast one is twice as slow, when the fast pointer is None It means that the intermediate node has been found: while fast.next is not None and fast.next.next is not None: slow = slow.next # slow pointer moves backward one position at a time fast = fast.next.next # fast pointer moves backward two positions at a time h = slow.next Q = reverse (h) # reverse to headless node linked list slow.next = None p = l while p is Not None and q is not None: if p.val is not q.val: return False q P = q.next, p.next if q is None: return True else: return False

Flashback linked list (header insertion): declare a header node, then traverse each node, and then insert the header into the linked list, a total of 4 steps

Step 1: save the node to which the current head node is directed only

Step 2: make the current node point to the node that the header node points to

Step 3: make the header node only to the current node

Step 4: point the pointer (p) to the next node and to the next loop

Head interpolation diagram:

Complete code:

# invert the single linked list def reverse (head) without a header node: h = ListNode (0) p = head while p is not None: X = p.next # saves the next node that the current node points to p.next = h.next # the current item points to the node pointed to the header node h.next = p # the header node points to the current node P = x # make the node point to the next node return h.next

Complete code

# palindromes linked list Input 1-> 2 output false, enter 1-> # linked list class class ListNode: def _ init__ (self, x): self.val = x self.next = None # string converted to linked list def list_node (s): lt = list (map (int) S.split ('')) l = ListNode (0) # create a linked list with a header node of 0 p = l for i in range (len (lt)): p.next = ListNode (lt [I]) p = p.next return l.next# invert a single linked list without a header node def reverse (head): h = ListNode (0) p = head while p is not None: X = p.next # holds the next node that the current node points to p.next = h.next# the current item points to the node h.next = p # the header node points to the current node p = x # so that the node points to the next node whether return h.next# is palindrome def palindrome (l): if l Is None: return True slow = fast = l # find intermediate nodes One fast and one slow pointer, the fast pointer is twice as slow, when the fast pointer is None It means that the intermediate node has been found: while fast.next is not None and fast.next.next is not None: slow = slow.next # slow pointer moves backward one position at a time fast = fast.next.next # fast pointer moves backward two positions at a time h = slow.next Q = reverse (h) # reverse to headless node linked list slow.next = None p = l while p is Not None and q is not None: if p.val is not q.val: return False q P = q.next, p.next if q is None: return True else: return Falseif _ _ name__ = ='_ main__': print ("palindromes linked list") l = list_node (input ()) print (palindrome (l))

Run result diagram:

What are the main application areas of python? 1. Cloud computing, typical application OpenStack. 2. WEB front-end development, many large websites are developed by Python. 3. Artificial intelligence applications, which are based on big data's analysis and deep learning, have essentially been unable to leave python. 4. System operation and maintenance project, the standard configuration of automatic operation and maintenance is python+Django/flask. 5. Financial management analysis, quantitative transaction, financial analysis. 6. Big data's analysis.

Thank you for your reading, the above is the whole content of "what is the method of Python judging palindromes linked list". Friends who learn to learn to hurry up to operate it. I believe that the editor will certainly bring you better quality articles. Thank you for your support to the website!

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.