leetCode The first 234 topic Palindrome list
link ：https://leetcode-cn.com/problems/palindrome-linked-list
Give you the head node of a single linked list head , Please judge whether the linked list is a palindrome linked list . If it is , return true ; otherwise , return false .
Example 1：
Input ：head = [1,2,2,1]
Output ：true
Example 2:
Input ：head = [1,2]
Output ：false
Tips ：
The number of nodes in the linked list is in the range [1, 105] Inside
0 <= Node.val <= 9
Advanced ： Can you use O(n) Time complexity and O(1) Space complexity to solve this problem ？
The simplest way to write this question is to use the double pointer method
Set up pointers at the head and tail , One move backward , One moves forward , But what this question gives is a single linked list instead of a double linked list , So the tail pointer cannot move forward .
Then we can first store all the elements of the linked list , Then reverse the new linked list , So the head pointer of the new linked list is the tail pointer we need , And be able to move it .
To reverse the linked list, please refer to section 206 topic , Portal
But this method will waste a lot of space , Because we need to store a linked list with identical values
## python3
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if head == None:
return False
if head.next == None:
return True
tail = head
headA = ListNode()
headA.val = head.val
tailA = headA
while tail.next != None:
tail = tail.next
temp = ListNode()
temp.val = tail.val
tailA.next = temp
tailA = tailA.next
headA = self.reverseList(headA)
while head.next != None:
if head.val != headA.val:
return False
headA = headA.next
head = head.next
return True
def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur != None:
ne = cur.next
cur.next = pre
pre = cur
cur = ne
return pre
The effect is not ideal either in time or space 
Advanced requirements We use it O(n) Time complexity and O(1) Spatial complexity solution
Then we should optimize the above code
-----------------------
The fatal flaw of the above code is that it copies an identical linked list because the tail pointer needs to move , The stop condition is that the entire linked list is traversed or there is an inequality .
In fact, we know that palindromes are symmetric from the middle , The stop condition is actually in the middle of traversing the linked list , To find inspiration .
If it is a palindrome linked list , Start symmetry in the middle , We might as well divide the linked list into two , Then reverse only the latter part . Because the reversal will change the direction of the original linked list and lose the head pointer of the original linked list , But after the linked list is divided into two , The previous fractional pointer and pointer are preserved , So there is no need to copy a linked list , You can operate in the last part of the original linked list .
----------------------
The next step is to find the node that can divide the linked list into two
We set the speed pointer , Go two steps at a time , Full pointer, one step at a time , Because the fast pointer is twice as fast as the full pointer , So when the fast pointer traverses , The full pointer is in the middle of the linked list .
When the linked list is even , Quick pointer to None, The full pointer is in the middle of the linked list , Same length before and after .
When the linked list is odd , The fast pointer points to the last element , And the slow pointer is just in the middle , At this time, you might as well move the slow pointer back one bit , It is divided into two , Make the list to be reversed shorter .
Then compare the elements of the two linked lists to determine whether the original linked list is a palindrome linked list
## python3
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
fast = head
slow = head
while fast != None and fast.next != None:
fast = fast.next.next
slow = slow.next
if fast != None:
slow = slow.next
slow = self.reverseList(slow)
fast = head
while slow != None:
if fast.val != slow.val:
return False
fast = fast.next
slow = slow.next
return True
def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur != None:
ne = cur.next
cur.next = pre
pre = cur
cur = ne
return pre
