题目:
给定单链表的头节点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)只会修改原本链表节点的指向