python-leetcode 23.回文链表

题目：

给定单链表的头节点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]，代码的执行流程如下：

1. front 初始化为 1。

2. 递归调用 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。

3. 最终返回 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)只会修改原本链表节点的指向