算法學習——快慢指針的作用及其應用場景

快慢指針的作用

針對連結清單的一些用法

快慢指針尋找連結清單中位數

初始時，快指針fast和慢指針slow均指向連結清單的左端點。我們将快指針fast向右移動兩次的同時，将慢指針slow向右移動一次，直到快指針到達邊界（即快指針到達右端點或快指針的下一個節點是右端點）。此時，慢指針slow對應的元素就是中位數。

// 知道右邊界
func getMid(left, right *Node) *Node {
     if left == nil {
        return nil
    }
    fast := left
    slow := left
    for ;fast != right && fast.Next != right; {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}
nil
// 不知道右邊界
func getMid(left *Node) *Node {
    if left == nil {
        return nil
    }
    fast := left
    slow := left
    for ;fast.Next != nil && fast.Next.Next != nil; {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

           

快慢指針尋找連結清單是否存在環

這裡實際上也是跟上面一樣，不過這裡的判斷條件就是如果存在fast==slow那就一定有環，沒有環的條件也就是fast到盡頭了

func isExsis(left *Node) bool {
    if head == nil {
        return false
    }
    fast := left
    slow := left
    for ;fast.Next != nil && fast.Next.Next != nil; {
        slow = slow.Next
        fast = fast.Next.Next
        if fast == slow {
            return true
        }
    }
    return false
}

           

快慢指針尋找連結清單環的入口

這裡的前提就是存在環哈，假定存在環的時候，這裡我們可以利用上之前的快慢指針fast 和 slow。這裡有個定理吧，當fast==slow時，将slow指向head，然後fast和slow一步步指向下一個節點，當兩個指針再次相等的時候就是這個環的入口了

證明啊，看這個連接配接吧

func isExsis(head *Node) *Node {
    if head == nil {
        return nil
    }
    fast := head
    slow := head
    for ;fast.Next != nil && fast.Next.Next != nil; {
        slow = slow.Next
        fast = fast.Next.Next
        if fast == slow {
            slow = head
            for ;slow != fast; {
                slow = slow.Next
                fast = fast.Next
            }
        }
    }
    return nil
}