python-leetcode 24.回文链表
题目：
给定单链表的头节点head,判断该链表是否为回文链表，如果是，返回True,否则，返回False
输入：head=[1,2,2,1]
输出：true
方法一：将值复制到数组中后用双指针法
有两种常用的列表实现，分别为数组列表和链表。
（1）数组列表底层是使用数组存储值，可以通过索引在O(1)的时间访问列表任何位置的值，这是基于内存寻址的方式。
（2）链表存储的是称为节点的对象，每个节点保存一个值和指向下一个节点的指针。访问某个特定索引的节点需要O(n)的时间，因为要通过指针获取到下一个位置的节点。
确定数组列表是否回文很简单，可以使用双指针法来比较两端的元素，并向中间移动。一个指针从起点向中间移动，另一个指针从终点向中间移动。这需要O(n)的时间，因为访问每个元素的时间是O(1),而有n个元素要访问
同样的方法在链表操作上并不简单，因为不论是正向访问还是反向访问都不是O(1).而将链表的值复制到数组列表中是O(n),因此简单的方法是将链表的值复制到数组列表中，再使用双指针法判断
算法：1.将链表复制到数组列表中 2.使用双指针法判断是否为回文
第一步：遍历链表将值复制到数组列表中。，使用currentNode 指向当前节点。每次迭代向数组添加currentNode.val，并更新currentNode = currentNode.next，当currentNode = null 时停止循环
第二步：使用双指针法来检查是否为回文。在起点放置一个指针，在结尾放置一个指针，每一次迭代判断两个指针指向的元素是否相同，若不同，返回 false；相同则将两个指针向内移动，并继续判断，直到两个指针相遇。但在 Python 中，很容易构造一个列表的反向副本进行比较。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):def isPalindrome(self, head):""":type head: Optional[ListNode]:rtype: bool"""vals=[] #初始化一个空列表来存储链表中的节点值current_node=head #创建一个指向链表头节点的引用while current_node is not None:vals.append(current_node.val) #将当前节点的值添加到列表中current_node=current_node.next #移动链表return vals==vals[::-1] #比较源列表和它的反转列表
时间复杂度：O(N)
空间复杂度：O(N)使用了一个数组列表存放链表的元素值
方法二：递归
如果使用递归反向迭代节点，同时使用递归函数外的变量向前迭代，就可以判断链表是否为回文
算法：currentNode指针先指到尾节点，由于递归的特性再从后往前进行比较。frontPointer是递归函数外的指针。若currentNode.val != frontPointer.val，则返回False,反之frontPointer向前移动并返回True。
对于输入 head = [1, 2, 2, 1]，代码的执行流程如下：
-
front初始化为1。 -
递归调用
recursively_check(1)：-
递归调用
recursively_check(2)：-
递归调用
recursively_check(2)：-
递归调用
recursively_check(1)：-
递归调用
recursively_check(None)，返回True。
-
-
比较
1和1，匹配，移动front到2，返回True。
-
-
比较
2和2，匹配，移动front到2，返回True。
-
-
比较
2和2，匹配，移动front到1，返回True。
-
-
最终返回
True，说明链表是回文
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):def isPalindrome(self, head):""":type head: Optional[ListNode]:rtype: bool"""self.front_pointer=head #记录链表的头节点def recursively_check(current_node=head): #定义一个递归函数，用递归遍历链表if current_node is not None: if not recursively_check(current_node.next): #递归来检查链表的下一个节点return False #任何一次递归返回False，则链表不是回文，函数返回 Falseif self.front_pointer.val !=current_node.val:#当前节点和链表前端节点的值是否相等。如果不相等，说明链表不是回文return Falseself.front_pointer=self.front_pointer.next #即指向链表的下一个节点。return True #当链表的所有节点都成功比较并且都匹配时，说明链表是回文return recursively_check()时间复杂度：O(N)
空间复杂度：O(N)
这种方法比第一中效果还差，因为对栈帧的开销大，并且有限。
方法三：快慢指针
将链表的后半部分反转，然后将前半部分和后半部分进行比较。
算法：1找到前半部分链表的尾节点。2反转后半部分链表。3判断是否回文。4恢复链表。5返回结果
执行步骤一：计算链表节点的数量，遍历链表找到前半部分的尾节点
使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
若链表个数为奇数，则中间的点应该属于前半部分
步骤二可以使用上一题反转链表的方式来反转链表的后半部分。
步骤三比较两个部分的值
步骤四使用步骤二的方式，反转恢复链表
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):def isPalindrome(self, head):""":type head: Optional[ListNode]:rtype: bool"""if head is None: #检查链表是否为空。如果为空return True #链表显然是回文first_half_end=self.end_of_first_half(head) #调用函数，找到链表前半部分的尾节点second_half_start=self.reverse_list(first_half_end.next) #开始反转链表的后半部分result=True #用于存储链表是否为回文的结果first_position=head #从链表头开始second_position=second_half_start #从反转后的链表的头开始while result and second_position is not None: #遍历链表的前部分和反转后的后半分，直到后部分遍历完if first_position.val != second_position.val:#比较当前两个节点的值，如果不相等result=Falsefirst_position=first_position.next #分别指向前半部分和后半部分的下一个节点second_position=second_position.nextfirst_half_end.next = self.reverse_list(second_half_start)#反转后半部分链表，恢复链表的原始顺序return result #返回最终的回文判断结果def end_of_first_half(self,head): #这个方法用于找到链表的前半部分的尾节点fast=headslow=headwhile fast.next is not None and fast.next.next is not None:fast=fast.next.nextslow=slow.nextreturn slowdef reverse_list(self,head):pre=Nonecurr=headwhile curr is not None:next_node=curr.nextcurr.next=prepre=currcurr=next_nodereturn pre时间复杂度：O(n)
空间复杂度：O(1)只会修改原本链表节点的指向