google seo网站 被k,沧州大型企业网站建设,羽毛球赛事级别分类,深圳黄页信息网题目#xff1a;
给定单链表的头节点head,判断该链表是否为回文链表#xff0c;如果是#xff0c;返回True,否则#xff0c;返回False 输入#xff1a;head[1,2,2,1]
输出#xff1a;true 方法一#xff1a;将值复制到数组中后用双指针法
有两种常用的列表实现#…题目
给定单链表的头节点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, val0, nextNone):
# self.val val
# self.next next
class Solution(object):def isPalindrome(self, head)::type head: Optional[ListNode]:rtype: boolvals[] #初始化一个空列表来存储链表中的节点值current_nodehead #创建一个指向链表头节点的引用while current_node is not None:vals.append(current_node.val) #将当前节点的值添加到列表中current_nodecurrent_node.next #移动链表return valsvals[::-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, val0, nextNone):
# self.val val
# self.next next
class Solution(object):def isPalindrome(self, head)::type head: Optional[ListNode]:rtype: boolself.front_pointerhead #记录链表的头节点def recursively_check(current_nodehead): #定义一个递归函数用递归遍历链表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_pointerself.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, val0, nextNone):
# self.val val
# self.next next
class Solution(object):def isPalindrome(self, head)::type head: Optional[ListNode]:rtype: boolif head is None: #检查链表是否为空。如果为空return True #链表显然是回文first_half_endself.end_of_first_half(head) #调用函数找到链表前半部分的尾节点second_half_startself.reverse_list(first_half_end.next) #开始反转链表的后半部分resultTrue #用于存储链表是否为回文的结果first_positionhead #从链表头开始second_positionsecond_half_start #从反转后的链表的头开始while result and second_position is not None: #遍历链表的前部分和反转后的后半分直到后部分遍历完if first_position.val ! second_position.val:#比较当前两个节点的值如果不相等resultFalsefirst_positionfirst_position.next #分别指向前半部分和后半部分的下一个节点second_positionsecond_position.nextfirst_half_end.next self.reverse_list(second_half_start)#反转后半部分链表恢复链表的原始顺序return result #返回最终的回文判断结果def end_of_first_half(self,head): #这个方法用于找到链表的前半部分的尾节点fastheadslowheadwhile fast.next is not None and fast.next.next is not None:fastfast.next.nextslowslow.nextreturn slowdef reverse_list(self,head):preNonecurrheadwhile curr is not None:next_nodecurr.nextcurr.nextpreprecurrcurrnext_nodereturn pre
时间复杂度O(n)
空间复杂度O(1)只会修改原本链表节点的指向
