快慢指针法的leetcode题目绘制
94 浏览量
2020-12-21
17:42:53
上传
评论
收藏 73KB PDF 举报
快慢指针法的快慢指针法的leetcode题目绘制题目绘制
双指针法，分为左右指针和快慢指针两种。其中左右指针在数组中运用较多，可以和滑窗法一起进行汇总：滑窗法运用
而快慢指针一般在链表中运用较多，在反转链表和定位链表节点及链表成环等逻辑中运用比较广泛。
141. 环形链表环形链表
逻辑非常简单，只要是环形的链表，那么快慢指针早晚会遇到。
值得注意的一点是，用try…except…来进行异常判定
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
try:
slow = head
fast = head.next
while fast is not slow:
fast = fast.next.next
slow = slow.next
return True
except:
return False
142. 环形链表环形链表 II
在上题的基础上，找到环形链表中环的起点，借用一张leetcode上的图。简单来说，由于兔子走两步，乌龟走一步，因此两者相遇时兔子走的距离是乌龟的一倍。
2distance(tortoise)=distance(hare) 2distance(tortoise) = distance(hare) 2distance(tortoise)=distance(hare)2(F+a)=F+a+b+a 2(F+a) =F+a+b+a 2(F+a)=F+a+b+aF=b F = b F=b
class Solution(object):
def detectCycle(self, head):
fast, slow = head, head
while True:
if not (fast and fast.next): return
fast, slow = fast.next.next, slow.next
#因此当两者相遇时，即图中的first intersection点时退出while循环
if fast == slow: break
#快指针重新移动到起点，两者同样的速度相遇时即为环的起点
fast = head
while fast != slow:
fast, slow = fast.next, slow.next
return fast
92. 反转链表反转链表 II
在之前的反转链表基础上，只反转一部分链表。因此可以引入两个指针分别定位需要反转链表的头和尾。中间反转链表后，和链表定位的头和尾重新连接即可。
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if m == n:
return head
dum = ListNode(-1)
#注意这一步指定链表的next
dum.next = head
a,c = dum,dum
for i in range(m-1):
a = a.next
for i in range(n):
c = c.next
b = a.next
d = c.next
pre = b
cur = pre.next
while cur != d:
next = cur.next
cur.next = pre
评论0