Python刷题模板——双指针技巧

快慢指针:判定链表中是否包含环

左右指针:解决数组(或者字符串)中的问题,比如二分查找

快慢指针

头节点head,快指针fast,慢指针slow

1.判断链表中是否含有环

两个指针,一个跑得快,一个跑得慢。如果不含有环,跑得快的那个指针最终会遇到NULL;如果含有环,快指针最终会超慢指针一圈,和慢指针相遇。

141. 环形链表

def hasCycle(self, head: ListNode) -> bool:
    fast = slow = head
    while fast != None and fast.next != None:
        fast = fast.next.next
        slow = slow.next
        if slow == fast: return True
    return False

2.已知链表中含有环,返回这个环的起始位置

当快慢指针相遇时,让其中任一个指针指向头节点,然后让它俩以相同速度前进,再次相遇时所在的节点位置就是环开始的位置

142. 环形链表 II

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = slow = head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                slow = head
                while slow != fast:
                    fast = fast.next
                    slow = slow.next
                return slow
        return None

3.寻找链表的中点

快指针一次前进两步,慢指针一次前进一步,当快指针到达链表尽头时,慢指针就处于链表的中间位置(奇数)或者中间的第二个位置(偶数)。

876. 链表的中间结点

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        fast = slow = head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
        return slow

4.寻找链表的倒数第n个节点

快指针先走n步,快慢指针再同时前进,快指针到链表尾时,慢指针所在位置为倒数第n个节点

19. 删除链表的倒数第N个节点

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        fast = slow = head
        for i in range(n):
            fast = fast.next
        if fast == None: # 为第一个节点
            return head.next
        while fast.next != None :
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

左右指针

数组中的索引值,left = 0,right = len(nums) – 1

1.二分查找

2.两数之和

167. 两数之和 II – 输入有序数组

3.反转数组(一般用list.reverse()就行)

344. 反转字符串

class Solution:
    def reverseString(self, s: List[str]) -> None:
        # s.reverse()
        left,right = 0,len(s) - 1
        while left < right:
            s[left],s[right] = s[right],s[left]
            left += 1
            right -= 1

4.滑动窗口算法

发表评论