LeetCode分類刷題之雙指針（快慢指針）

1.判斷連結清單是否存在環

https://leetcode-cn.com/problems/linked-list-cycle/

解題思路：這一題在思路上有點類似之前的尋找連結清單公共節點的做法，環問題可以了解為國小數學的追及問題，如果跑道是環形的，那麼兩個運動員一快一慢，跑的快的總會在某一個點追上跑的慢的，同樣走的快的指針在存在環的連結清單上總會有追上走的慢的指針的時候，如果兩個指針能相遇那麼連結清單必定存在環。

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

2.移動零

https://leetcode-cn.com/problems/move-zeroes/submissions/

解題思路：fast指針先行探路，當檢測到不為零的數，就和slow指針交換資料，同時slow指針向前移動一步

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1
           

3.移除元素

https://leetcode-cn.com/problems/remove-element/

解題思路：和移動0的問題類似，将目标數字全部移動到末尾即可

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if not nums: return 0
        slower, faster = 0, 0
        while faster < len(nums):
            if nums[slower] != val: slower += 1
            elif nums[faster] != val: 
                nums[slower], nums[faster] = nums[faster], nums[slower]
                slower += 1
            faster += 1
        return slower    
           

4.删除排序數組的重複項

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

解題思路：還是快慢指針，fast先出發搜尋，如果fast的值不等于slow的話，先讓slow走一步保留一個重複元素，然後交換slow和fast的值。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not  nums: return 0

        slower, faster = 0, 0
        while faster< len(nums):
        #當快指針指向的元素與慢指針不同時，說明相同的元素已經周遊結束，此時将慢指針後移，将快指針的元素寫入慢指針位置，保留一個元素
            if nums[slower] != nums[faster]:
                slower += 1
                nums[slower] = nums[faster]
            faster += 1
        return slower + 1
           

5.删除排序數組的重複項（加強版）

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/

解題思路：在上一題的基礎上，多加一個标志位，

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums: return 0
        flag = True
        slower, faster = 0, 1
        while faster <len(nums):
            if nums[slower] != nums[faster]:
                slower += 1
                nums[slower] = nums[faster]
                flag = True
            else:
                if flag:
                    slower += 1
                    nums[slower] = nums[faster]
                    flag = False
            faster += 1 
        return slower + 1