19. Remove Nth Node From End of List

題目連結

思路

此題是要根據題目輸入的 n 值由後往前數將指定的節點給刪除，本題的解題思路和子陣列總和這題有點接近，會需要利用到雙指標不斷進行夾擠並檢查兩個指標之間的差距是否抵達門檻值，並在結尾指標走到最後的時候進行移除節點的操作。

在此題裡面也會使用 dummy 作為虛擬的開頭節點以便後續的操作，而主要需要思考的部分起始和結尾指標的移動原則，以及距離的計算標準。結尾指標的作用是單純的一路的向後推進直到遇到 null 為止，而起始指標則是需要在過程中檢查它和結尾指標的距離是否超過門檻，若超過則往前移動直到距離小於門檻。

至於這個門檻值當然就和題目所輸入的 n 有關聯了~ 不過需要注意的是，這裡再檢查兩個指標的距離時如果以 n 作為基準的話，等到結尾指標碰到 null 的時候起始指標如果停在距離 n 個節點的位置的話，後續要進行移除操作時會產生一些困難 (因為要移除該節點的做法是要將它前一個節點指向它的後一個節點)，因此應該要讓起始節點停在要刪除節點的前面，後續再進行移除的操作就可以了~

Full Code

Golang

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if head.Next == nil {
        return nil
    }
  
    dummy := &ListNode{-1, head}
    prev := dummy
    cur := dummy.Next
    diff := 1

    for cur != nil {
        cur = cur.Next
        diff++

        if diff > n + 1 {
            prev = prev.Next
            diff--
        }
    }

    prev.Next = prev.Next.Next

    return dummy.Next
}