青岛哪里有做网站公司的,长沙网站设计咨询电话,虚拟主机做视频网站可以吗,网站后台是什么意思leetcode-explore-learn-数据结构-链表31.反转一个链表2.移除链表元素3.奇偶链表4.回文链表5.小结本系列博文为leetcode-explore-learn子栏目学习笔记#xff0c;如有不详之处#xff0c;请参考leetcode官网#xff1a;https://leetcode-cn.com/explore/learn/card/linked-l…
leetcode-explore-learn-数据结构-链表31.反转一个链表2.移除链表元素3.奇偶链表4.回文链表5.小结本系列博文为leetcode-explore-learn子栏目学习笔记如有不详之处请参考leetcode官网https://leetcode-cn.com/explore/learn/card/linked-list/所有例题的编程语言为python
1.反转一个链表
leetcode 206 思路1 迭代求解将当前结点next信息保存下来然后将前一个节点的信息存入当前结点的next中。更新当前结点。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution(object):def reverseList(self, head)::type head: ListNode:rtype: ListNodeif headNone:return headpre_nodeNonecur_nodeheadwhile(cur_node):next_nodecur_node.nextcur_node.nextpre_nodepre_nodecur_nodecur_nodenext_nodereturn pre_node 思路2 递归假设链表的其余部分都已经被翻转现在该如何翻转它前面的部分。由最后一个开始往前不断翻转
class Solution(object):def reverseList(self, head)::type head: ListNode:rtype: ListNodeif headNone or head.nextNone:return headpself.reverseList(head.next) # 记录最后一个结点作为头指针用的。head.next.nextheadhead.nextNonereturn p2.移除链表元素
删除链表中等于给定值 val 的所有节点。 思路遍历链表的每一结点如果值等于给定值将其删除即可。 注意点要删除链表节点时可以使用哑结点技巧防止删原链表的头结点。最后返回时返回dummy.next即可。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution(object):def removeElements(self, head, val)::type head: ListNode:type val: int:rtype: ListNodedummyListNode(0)dummy.nextheadpre_nodedummycur_nodedummy.nextwhile(cur_node):next_nodecur_node.nextif cur_node.valval:pre_node.nextnext_node # 删除结点else:pre_nodecur_nodecur_nodenext_nodereturn dummy.next
3.奇偶链表
给定一个单链表把所有奇数节点和偶数节点节点 编号的奇偶性分别排在一起。 思路1原来的链表分成奇偶两个子链表然后将偶链表链接到奇链表后面。 没有使用额外的空间直接从原来的链表中截取。
# Definition for singly-linked list.
class ListNode(object):def __init__(self, x):self.val xself.next Noneclass Solution(object):def oddEvenList(self, head)::type head: ListNode:rtype: ListNodeif headNone:return headeven_hListNode(0)even_nodeeven_hcur_nodeheadi1while(cur_node):next_nodecur_node.nextif i %20:cur_node.nextNone # 将node.next的值给设置为零能防止成环even_node.nextcur_nodeeven_nodeeven_node.nextpre_node.nextnext_nodeelse:pre_nodecur_nodecur_nodenext_nodei1cur_nodehead.nextpre_nodeheadwhile(cur_node):print(pre_node.val)pre_nodecur_nodecur_nodecur_node.nextpre_node.nexteven_h.nextreturn head 4.回文链表
判断一个链表是否为回文链表。 o(n)时间复杂度o(1)空间复杂度
思路1可以先把链表装进数组中判断数组中元素是否构成回文。数组的前后遍历比单链表方便。时间复杂度o(n)空间复杂度o(n)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution(object):def isPalindrome(self, head)::type head: ListNode:rtype: boolif not head or not head.next:return Truelst[]pheadwhile(p):lst.append(p.val)pp.nextreturn lstlst[::-1]思路2翻转原链表对照两个链表是否一致如果回文链表应该是一致的反之原链表不为回文链表。时间复杂度o(n),空间复杂度o(n)
# Definition for singly-linked list.
class ListNode(object):def __init__(self, x):self.val xself.next Noneclass Solution(object):def isPalindrome(self, head)::type head: ListNode:rtype: boolif headNone or head.nextNone:return True# 备份原链表head_beListNode(0)nodeheadnode_behead_be while(node):node_be.nextListNode(node.val)node_benode_be.nextnodenode.next# 转置原链表pre_nodeNonecur_nodeheadwhile(cur_node):next_nodecur_node.nextcur_node.nextpre_nodepre_nodecur_nodecur_nodenext_node# 比较两个链表node_behead_be.nextnode_afpre_nodewhile(node_be and node_af):if node_be.val!node_af.val:return Falsenode_benode_be.nextnode_afnode_af.nextreturn True思路三避免使用 O(n)O(n) 额外空间的方法就是改变输入。
我们可以将链表的后半部分反转修改链表结构然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例因为使用该函数的人不希望链表结构被更改。
class Solution(object):def isPalindrome(self, head)::type head: ListNode:rtype: boolif not head or not head.next:return True# 计算链表长度p1headn1while(p1.next):p1p1.nextn1p1headp2headif n2:if head.valhead.next.val:return Trueelse:return False# 找链表中点for i in range(int(round(n/2.0))-1): # 0p1p1.nexthalf_endp1 # 前一半链表的最后一个节点# 翻转后一半链表p1p1.nextpre_nodeNonefor i in range(int(n/2.0)): # 0,1next_nodep1.nextp1.nextpre_nodepre_nodep1p1next_nodehalf_end.nextpre_nodep1head# 比较前一半和翻转后的后一半。for i in range(int(round(n/2.0))): # 0,1p1p1.nextfor i in range(int(n/2)):# 0,1if p1.val!p2.val:return Falsep1p1.nextp2p2.nextreturn True5.小结
1.使用链表时不易调试自己多尝试几个测试用例总是很有用的通过输出链表节点的值来观测代码运行情况。
2.多指针时为指针设定合适的名称防止自己被搞混
3.单链表操作时储存前一个节点的信息往往是有效的。
