如何做视频教程网站,惠州seo外包平台,七牛云服务,陕西建设工程信息网站1.相交链表
解题思路 快慢指针#xff1a;分别求出两个链表的长度n1和n2#xff0c;在长度较长的那个链表上#xff0c;快指针先走n2 - n1#xff0c;慢指针再出发#xff0c;最后能相遇则链表相交 时间复杂度O(mn)#xff0c;空间复杂度O(1)代码# Definition for singl…1.相交链表
解题思路 快慢指针分别求出两个链表的长度n1和n2在长度较长的那个链表上快指针先走n2 - n1慢指针再出发最后能相遇则链表相交 时间复杂度O(mn)空间复杂度O(1)代码# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) - Optional[ListNode]:if not headA or not headB:return Nonel_a 0l_b 0node headAwhile node:l_a 1node node.nextnode headBwhile node:l_b 1node node.nextnode1 headA node2 headBif l_b l_a:l_a, l_b l_b, l_anode1, node2, node2, node1for _ in range(l_a - l_b):node1 node1.nextwhile node1 and node2:if node1 node2:return node1node1 node1.nextnode2 node2.nextreturn None2.翻转链表
解题思路 最基本的题目一定要掌握。prev初始化成None不需要dummy_head 时间复杂度ON空间复杂度O1代码class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:if not head:return head# prev直接初始化成None就好prev Nonecur headnex Nonewhile cur:nex cur.nextcur.next prevprev curcur nexreturn prev3.回文链表
解题思路 查找中间链表然后翻转后半段接着使用双指针比较判断即可 时间复杂度ON空间复杂度O1代码# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def isPalindrome(self, head: Optional[ListNode]) - bool:def reverse(head):if not head:return headprev Nonecur headnex Nonewhile cur:nex cur.nextcur.next prevprev curcur nexreturn previf not head:return Falseif not head.next:return Trueslow headfast head.nextwhile fast and fast.next:slow slow.nextfast fast.next.nexthead2 reverse(slow.next)node_1 headnode_2 head2while node_1 and node_2:if node_1.val ! node_2.val:return Falsenode_1 node_1.nextnode_2 node_2.nextreturn True4. 环形链表
题目描述 判断链表是否有环解题思路 快慢指针快指针一次走一步慢指针一次走两步如果有环的话他们一定在环中相遇。类比于操场跑圈的套圈对于slow来说fast是一个节点一个节点的靠近slow的 时间复杂度O(N) 空间复杂度O(1)。代码class Solution:def hasCycle(self, head: Optional[ListNode]) - bool:if not head or not head.next:return Falsefast slow headwhile fast and fast.next:slow slow.nextfast fast.next.nextif slow fast:return Truereturn False5. 环形链表2
题目描述 如果链表有环需要返回入环的节点无环返回None解题思路 图片来自代码随想录查找是否有环和上一题目一样使用快慢指针如果有环那么他们一定在环内相遇。如下图所示慢指针走过的路程是x y快指针走过的路程是 x y (y z) * n又因为快指针走的路程是慢指针的两倍因此有x y (y z) * n 2* (x y), 也就是(y z) * n x y, 也就是(yz)*(n-1) z x那么如果两个节点分别从头结点和相遇节点出发一定可以在入口节点处相遇 时间复杂度O(N) 空间复杂度O(1)。代码class Solution:def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]:if not head or not head.next:return Noneslow fast headhas_cycle Falsewhile fast and fast.next:slow slow.nextfast fast.next.nextif fast slow:has_cycle Truebreakif not has_cycle:return Nonenode1 headnode2 slowwhile node1 ! node2:node1 node1.nextnode2 node2.nextreturn node16. 合并两个有序链表
解题思路 是链表排序和合并K个有序链表等题目要用的基本模块 时间复杂度O(nm) 空间复杂度O(nm)代码# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) - Optional[ListNode]:if not list1:return list2if not list2:return list1head ListNode()cur headnode1 list1node2 list2while node1 and node2:if node1.val node2.val:cur.next node1node1 node1.nextelse:cur.next node2node2 node2.nextcur cur.nextif node1:cur.next node1if node2:cur.next node2return head.next7. 两数相加 题目描述 解题思路 注意考虑进位、两个数字位数不同的情况 时间复杂度O(max(m,n))其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置而处理每个位置只需要 O(1) 的时间。 空间复杂度O(1)。注意返回值不计入空间复杂度。 代码 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]:if not l1:return l2if not l2:return l1prev 0n1 n2 0new_head ListNode()node1 l1node2 l2cur new_headwhile node1 or node2:n1 node1.val if node1 else 0n2 node2.val if node2 else 0s n1 n2 prevnode ListNode(s % 10)prev s // 10cur.next nodecur cur.nextif node1:node1 node1.nextif node2:node2 node2.nextif prev ! 0:node ListNode(prev)cur.next nodereturn new_head.next8. 删除链表的倒数第N个节点
解题思路 快慢指针快指针先走N然后快慢一起走当快指针走到末尾时慢指针指向的就是要删除的节点代码# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:if not head:return Nonenew_head ListNode(0, head)prev new_headslow fast headfor i in range(n):if not fast:raise ValueError(n must greter than length of list)fast fast.nextwhile fast:prev slowslow slow.nextfast fast.nextprev.next slow.nextreturn new_head.next9. 两两交换链表中的节点
题目描述 给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。解题思路 模拟两两交换的过程即可代码class Solution:def swapPairs(self, head: Optional[ListNode]) - Optional[ListNode]:if not head:return headnew_head ListNode(nexthead)cur headprev new_headwhile cur and cur.next:next cur.nextcur.next next.nextnext.next curprev.next nextprev curcur prev.nextreturn new_head.next10. k个一组翻转链表 题目描述 给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。 k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。 解题思路 将前k个节点切断成一个链表进行翻转并递归对剩下的链表进行‘k个一组翻转链表’操作再将两个链表连起来即可 代码 class Solution:def reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]:def reverse(head):if not head:return headprev Nonecur headnex Nonewhile cur:nex cur.nextcur.next prevprev curcur nexreturn previf not head:return headl 0node headwhile node:l 1node node.nextif l k:return headnode headfor i in range(k - 1):node node.nextnew_head node.nextnode.next Nonereverse_head reverse(head)head.next self.reverseKGroup(new_head, k)return reverse_head11. 随机链表的复制
解题思路 第一遍循环复制每个节点并把他们通过next连接成一个普通的链表同时构建哈希表哈希表的key是旧的节点value是复制的节点 第二遍循环通过哈希表完成random的指定注意random可能是空的 时间复杂度O(N), 空间复杂度O(N)代码class Solution:def copyRandomList(self, head: Optional[Node]) - Optional[Node]:if not head:return headdic {}node headnew_head Node(0)prev new_headwhile node:new_node Node(xnode.val)prev.next new_nodedic[node] new_nodeprev new_nodenode node.nextnode headwhile node:# 一定要注意原始节点的random是不是空的if node.random:dic[node].random dic[node.random]node node.nextreturn new_head.next12. 排序链表 题目描述 解题思路 解题思路归并排序的思想找到中间节点然后分别对左右两边进行排序最后合并左右两边的有序链表。 这道题目的关键1. 找到链表的中间节点用快慢指针实现慢指针一次走一步快指针一次走两步当快指针走到末尾时慢指针指向的就是中间节点不用求出链表长度再计算中间节点的位置2.将链表从中间节点切断成两个链表3. 合并两个有序链表。 时间复杂度O(nlogn)其中 n 是链表的长度。 空间复杂度O(logn)其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。 代码 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def sortList(self, head: Optional[ListNode]) - Optional[ListNode]:def merge(l1, l2):if not l1:return l2if not l2:return l1head ListNode()cur headnode1 l1node2 l2while node1 and node2:if node1.val node2.val:cur.next node1node1 node1.nextelse:cur.next node2node2 node2.nextcur cur.nextif node1:cur.next node1if node2:cur.next node2return head.nextif not head or not head.next:return head# 找到中间节点的方法快慢指针slow headfast head.nextwhile fast and fast.next:slow slow.nextfast fast.next.nextnode1 headnode2 slow.next# 从中间断开链表slow.next Nonehead1 self.sortList(node1)head2 self.sortList(node2)return merge(head1, head2)13. 合并k个升序链表
题目描述 给你一个链表数组每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中返回合并后的链表。解题思路 分治通过递归两两合并其中会用到合并两个有序链表这个函数在上一个题目排序链表中也用到了因此这个模块函数要掌握好代码class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]:def merge(l1, l2):if not l1:return l2if not l2:return l1head ListNode()cur headnode1 l1node2 l2while node1 and node2:if node1.val node2.val:cur.next node1node1 node1.nextelse:cur.next node2node2 node2.nextcur cur.nextif node1:cur.next node1if node2:cur.next node2return head.nextn len(lists)if n 0:return Noneif len(lists) 1:return lists[0]mid n // 2head1 self.mergeKLists(lists[: mid])head2 self.mergeKLists(lists[mid :])return merge(head1, head2)13 LRU
题目描述 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类 LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。解题思路 哈希表 双向链表。哈希表用于快速查找节点双向链表用于存储使用情况最近被使用的节点被放在双向链表的后端 时间复杂度 O(1) 空间复杂度O(capacity)。 注意python的字典删除元素的方法是pop(key[,default]) 删除字典给定键 key 所对应的值返回值为被删除的值。key值必须给出。 否则返回default值。代码class BiNode:def __init__(self, val0, nextNone, prevNone, keyNone):self.val valself.next nextself.prev prevself.key keyclass LRUCache:def __init__(self, n):self.n nself.dic {}self.head BiNode()self.tail BiNode()self.head.next self.tailself.tail.prev self.headdef add_node_to_tail(self, node):self.tail.prev.next nodenode.prev self.tail.prevnode.next self.tailself.tail.prev nodedef rm_node(self, node):prev node.prevnex node.nextprev.next nexnex.prev prevdef get(self, key):if key in self.dic:self.rm_node(self.dic[key])self.add_node_to_tail(self.dic[key])return self.dic[key].valelse:return -1def put(self, key, value):if key in self.dic:self.dic[key].val valueself.rm_node(self.dic[key])self.add_node_to_tail(self.dic[key])else:if len(self.dic) self.n:to_delete self.head.nextself.rm_node(to_delete)self.dic.pop(to_delete.key)new_node BiNode()new_node.val valuenew_node.key keyself.dic[key] new_nodeself.add_node_to_tail(new_node)# Your LRUCache object will be instantiated and called as such:
# obj LRUCache(capacity)
# param_1 obj.get(key)
# obj.put(key,value)总结
对于链表题目主要的解题思路有快慢指针、翻转链表局部、合并有序链表、查找中间位置的链表节点、将长链表分解切断成小的链表分治。 需要熟练掌握的模块翻转链表、合并有序链表、查找中间位置的链表节点 查找中间位置的链表节点使用快慢指针
slow head
fast head.next
while fast and fast.next:slow slow.nextfast fast.next.next
