5、雙指針技巧套路框架——Go語言版

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool{
    for head != nil{
		head = head.Next
    }
    return false
}

但是如果鏈表中含有環，那麼這個指針就會陷入死循環，因為環形數組中沒有 null 指針作為尾部節點。

經典解法就是用兩個指針，一個跑得快，一個跑得慢。如果不含有環，跑得快的那個指針最終會遇到 null，說明鏈表不含環；如果含有環，快指針最終會超慢指針一圈，和慢指針相遇，說明鏈表含有環。

/** 141
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    var fast, slow *ListNode
    fast = head
    slow = head
    for fast != nil && fast.Next != nil{
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow{
            return true
        }
    }
    return false
}

2、已知鏈表中含有環，返回這個環的起始位置

這個問題一點都不困難，有點類似腦筋急轉彎，先直接看程式碼：

// 142
func detectCycle(head *ListNode) *ListNode{
    var fast, slow *ListNode
    fast = head
    slow = head
    for fast != nil && fast.Next != nil{
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow{
            break
        }
    }
    // 上面的程式碼類似 hasCycle函數
    if fast == nil || fast.Next == nil{
        // fast 遇到空指針說明沒有環
        return nil
    }
    slow = head
    for slow != fast{
        fast = fast.Next
        slow = slow.Next
    }
    return slow
}

可以看到，當快慢指針相遇時，讓其中任一個指針指向頭節點，然後讓它倆以相同速度前進，再次相遇時所在的節點位置就是環開始的位置。這是為什麼呢？

第一次相遇時，假設慢指針 slow 走了 k 步，那麼快指針 fast 一定走了 2k 步，也就是說比 slow 多走了 k 步（也就是環的長度）。

設相遇點距環的起點的距離為 m，那麼環的起點距頭結點 head 的距離為 k – m，也就是說如果從 head 前進 k – m 步就能到達環起點。

巧的是，如果從相遇點繼續前進 k – m 步，也恰好到達環起點。

所以，只要我們把快慢指針中的任一個重新指向 head，然後兩個指針同速前進，k – m 步後就會相遇，相遇之處就是環的起點了。

3、尋找鏈表的中點

類似上面的思路，我們還可以讓快指針一次前進兩步，慢指針一次前進一步，當快指針到達鏈表盡頭時，慢指針就處於鏈表的中間位置。

for fast != nil && fast.next != nil{
	fast = fast.next.next
    slow = slow.next
}
// slow 就在中間位置
return slow

當鏈表的長度是奇數時，slow 恰巧停在中點位置；如果長度是偶數，slow 最終的位置是中間偏右：

尋找鏈表中點的一個重要作用是對鏈表進行歸併排序。

回想數組的歸併排序：求中點索引遞歸地把數組二分，最後合併兩個有序數組。對於鏈表，合併兩個有序鏈表是很簡單的，難點就在於二分。

但是現在你學會了找到鏈表的中點，就能實現鏈表的二分了。關於歸併排序的具體內容本文就不具體展開了。

4、尋找鏈表的倒數第 k 個元素

我們的思路還是使用快慢指針，讓快指針先走 k 步，然後快慢指針開始同速前進。這樣當快指針走到鏈表末尾 null 時，慢指針所在的位置就是倒數第 k 個鏈表節點（為了簡化，假設 k 不會超過鏈表長度）：

var slow,fast *ListNode
slow = fast = head
for k-- > 0{
    fast = fast.next
}
for fast != nil{
	slow = slow.next
    fast = fast.next
}
return slow

二、左右指針的常用演算法

左右指針在數組中實際是指兩個索引值，一般初始化為 left = 0, right = nums.length – 1 。

1、二分查找

前文「二分查找」有詳細講解，這裡只寫最簡單的二分演算法，旨在突出它的雙指針特性：

// 704
func search(nums []int, target int) int{
    left := 0
    right := len(nums) - 1
    for left <= right{
        mid := (right + left) / 2
        if nums[mid] == target{
            return mid
        }else if nums[mid] < target{
            left = mid + 1
        }else{
            right = mid -1
        }
    }
    return -1
}

2、兩數之和

直接看一道 LeetCode 題目吧：

只要數組有序，就應該想到雙指針技巧。這道題的解法有點類似二分查找，通過調節 left 和 right 可以調整 sum 的大小：

// 167
func twoSum(numbers []int, target int) []int {
    // 左右指針在數組的兩端初始化
    left := 0
    right := len(numbers)-1
    for left < right{
        sum := numbers[left] + numbers[right]
        if sum == target{
            // 題目要求的索引是從1開始的
            return []int{left+1, right+1}
        }else if sum < target{
            left++   // 讓sum大一點
        }else{
            right--  // 讓sum小一點
        }
    }
    return []int{-1, -1}
}

3、反轉數組

func reverse(nums []int){
    left := 0
    right := len(nums) - 1
    for left < right{
        // 交換nums[left]和nums[right]
        temp := nums[left]
        nums[left] = nums[right]
        nums[right] = temp
        left++
        right--
    }
}

4、滑動窗口演算法

這也許是雙指針技巧的最高境界了，如果掌握了此演算法，可以解決一大類子字元串匹配的問題，不過「滑動窗口」稍微比上述的這些演算法複雜些。

幸運的是，這類演算法是有框架模板的，將在後面講解了「滑動窗口」演算法模板，幫大家秒殺幾道 LeetCode 子串匹配的問題。

Tags: golang