欧美日韩中文字幕,中文字幕在线亚洲24

跳表的定義

跳表(SkipList)：增加了向前指針的鏈表叫做跳表。跳表全稱(chēng)叫做跳躍表，簡(jiǎn)稱(chēng)跳表。跳表是一個(gè)隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，實(shí)質(zhì)是一種可以進(jìn)行近似二分查找的有序鏈表。跳表在原有的有序鏈表上增加了多級(jí)索引，通過(guò)索引來(lái)實(shí)現(xiàn)快速查詢。跳表不僅能提高搜索性能，同時(shí)也可以提高插入和刪除操作的性能。

跳表的詳解

有序原始鏈表

對(duì)于一個(gè)單鏈表來(lái)說(shuō)，即使鏈表中的數(shù)據(jù)是有序的，如果我們想要查找某個(gè)數(shù)據(jù)，也必須從頭到尾的遍歷鏈表，很顯然這種查找效率是十分低效的，時(shí)間復(fù)雜度為O(n)。
那么我們?nèi)绾翁岣卟檎倚誓?？我們可以?duì)鏈表建立一級(jí)“索引”，每?jī)蓚€(gè)結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)到上一級(jí)，我們把抽取出來(lái)的那一級(jí)叫做索引或者索引層，如下圖所示，我建立了兩級(jí)索引，down表示down指針。

image.png

假設(shè)我們現(xiàn)在要查找值為16的這個(gè)結(jié)點(diǎn)。我們可以先在索引層遍歷，當(dāng)遍歷索引層中值為13的時(shí)候，通過(guò)值為13的結(jié)點(diǎn)的指針域發(fā)現(xiàn)下一個(gè)結(jié)點(diǎn)值為17，因?yàn)殒湵肀旧碛行?，所以值?6的結(jié)點(diǎn)肯定在13和17這兩個(gè)結(jié)點(diǎn)之間。然后我們通過(guò)索引層結(jié)點(diǎn)的down指針，下降到原始鏈表這一層，繼續(xù)往后遍歷查找。這個(gè)時(shí)候我們只需要遍歷2個(gè)結(jié)點(diǎn)（值為13和16的結(jié)點(diǎn)），就可以找到值等于16的這個(gè)結(jié)點(diǎn)了。如果使用原來(lái)的鏈表方式進(jìn)行查找值為16的結(jié)點(diǎn)，則需要遍歷10個(gè)結(jié)點(diǎn)才能找到，而現(xiàn)在只需要遍歷7個(gè)結(jié)點(diǎn)即可，從而提高了查找效率。

那么我們可以由此得到啟發(fā)，和上面建立第一級(jí)索引的方式相似，在第一級(jí)索引的基礎(chǔ)上，每?jī)蓚€(gè)一級(jí)索引結(jié)點(diǎn)就抽到一個(gè)結(jié)點(diǎn)到第二級(jí)索引中。再來(lái)查找值為16的結(jié)點(diǎn)，只需要遍歷6個(gè)結(jié)點(diǎn)即可，從而進(jìn)一步提高了查找效率。

跳表的時(shí)間復(fù)雜度

單鏈表的查找時(shí)間復(fù)雜度為：O(n)，
下面分析下跳表這種數(shù)據(jù)結(jié)構(gòu)的查找時(shí)間復(fù)雜度：
我們首先考慮這樣一個(gè)問(wèn)題，如果鏈表里有n個(gè)結(jié)點(diǎn)，那么會(huì)有多少級(jí)索引呢？按照上面講的，每?jī)蓚€(gè)結(jié)點(diǎn)都會(huì)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)。那么第一級(jí)索引的個(gè)數(shù)大約就是n/2，第二級(jí)的索引大約就是n/4，第三級(jí)的索引就是n/8，依次類(lèi)推，也就是說(shuō)，第k級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)是第k-1級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)的1/2，那么第k級(jí)的索引結(jié)點(diǎn)個(gè)數(shù)為n/(2k)。

、】
`
假設(shè)索引有h級(jí)，最高級(jí)的索引有2個(gè)結(jié)點(diǎn)，通過(guò)上面的公式，我們可以得到，從而可得：h =log2n-1。如果包含原始鏈表這一層，整個(gè)跳表的高度就是。我們?cè)谔碇胁檎夷硞€(gè)數(shù)據(jù)的時(shí)候，如果每一層都要遍歷m個(gè)結(jié)點(diǎn)，那么在跳表中查詢一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度就為O(m*logn)。

其實(shí)根據(jù)前面的分析，我們不難得出m=3，即每一級(jí)索引都最多只需要遍歷3個(gè)結(jié)點(diǎn)，分析如下：

時(shí)間復(fù)雜度分析

如上圖所示，假如我們要查找的數(shù)據(jù)是x，在第k級(jí)索引中，我們遍歷到y(tǒng)結(jié)點(diǎn)之后，發(fā)現(xiàn)x大于y，小于y后面的結(jié)點(diǎn)z。所以我們通過(guò)y的down指針，從第k級(jí)索引下降到第k-1級(jí)索引。在第k-1級(jí)索引中，y和z之間只有3個(gè)結(jié)點(diǎn)(包含y和z)。所以，我們?cè)趉-1級(jí)索引中最多需要遍歷3個(gè)結(jié)點(diǎn)，以此類(lèi)推，每一級(jí)索引都最多只需要遍歷3個(gè)結(jié)點(diǎn)。

因此，m=3，所以跳表查找任意數(shù)據(jù)的時(shí)間復(fù)雜度為O(logn)，這個(gè)查找的時(shí)間復(fù)雜度和二分查找是一樣的，但是我們卻是基于單鏈表這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的。不過(guò)，天下沒(méi)有免費(fèi)的午餐，這種查找效率的提升是建立在很多級(jí)索引之上的，即空間換時(shí)間的思想。其具體空間復(fù)雜度見(jiàn)下文詳解。

跳表的空間復(fù)雜度

比起單純的單鏈表，跳表就需要額外的存儲(chǔ)空間去存儲(chǔ)多級(jí)索引。假設(shè)原始鏈表的大小為n，那么第一級(jí)索引大約有n/2個(gè)結(jié)點(diǎn)，第二級(jí)索引大約有4/n個(gè)結(jié)點(diǎn)，依次類(lèi)推，每上升一級(jí)索引結(jié)點(diǎn)的個(gè)數(shù)就減少一半，直到剩下最后2個(gè)結(jié)點(diǎn)，如下圖所示，其實(shí)就是一個(gè)等比數(shù)列。

空間復(fù)雜度

這幾級(jí)索引結(jié)點(diǎn)總和為：n/2 + n/4 + n/8 + ... + 8 + 4 + 2 = n - 2。所以跳表的空間復(fù)雜度為O(n)。也就是說(shuō)如果將包含n個(gè)結(jié)點(diǎn)的單鏈表構(gòu)造成跳表，我們需要額外再用接近n個(gè)結(jié)點(diǎn)的存儲(chǔ)空間。

其實(shí)從上面的分析，我們利用空間換時(shí)間的思想，已經(jīng)把時(shí)間壓縮到了極致，因?yàn)槊恳患?jí)每?jī)蓚€(gè)索引結(jié)點(diǎn)就有一個(gè)會(huì)被抽到上一級(jí)的索引結(jié)點(diǎn)中，所以此時(shí)跳表所需要的額外內(nèi)存空間最多，即空間復(fù)雜度最高。其實(shí)我們可以通過(guò)改變抽取結(jié)點(diǎn)的間距來(lái)降低跳表的空間復(fù)雜度，在其時(shí)間復(fù)雜度和空間復(fù)雜度方面取一個(gè)綜合性能，當(dāng)然也要看具體情況，如果內(nèi)存空間足夠，那就可以選擇最小的結(jié)點(diǎn)間距，即每?jī)蓚€(gè)索引結(jié)點(diǎn)抽取一個(gè)結(jié)點(diǎn)到上一級(jí)索引中。如果想降低跳表的空間復(fù)雜度，則可以選擇每三個(gè)或者每五個(gè)結(jié)點(diǎn)，抽取一個(gè)結(jié)點(diǎn)到上級(jí)索引中。

image.png

如上圖所示，每三個(gè)結(jié)點(diǎn)抽取一個(gè)結(jié)點(diǎn)到上一級(jí)索引中，則第一級(jí)需要大約n/3個(gè)結(jié)點(diǎn)，第二級(jí)索引大約需要n/9個(gè)結(jié)點(diǎn)。每往上一級(jí)，索引的結(jié)點(diǎn)個(gè)數(shù)就除以3，為了方便計(jì)算，我們假設(shè)最高一級(jí)的索引結(jié)點(diǎn)個(gè)數(shù)為1，則可以得到一個(gè)等比數(shù)列，去下圖所示：

image.png

通過(guò)等比數(shù)列的求和公式，總的索引結(jié)點(diǎn)大約是：n/3 + n /9 + n/27 + ... + 9 + 3 + 1 = n/2。盡管空間復(fù)雜度還是O(n)，但是比之前的每?jī)蓚€(gè)結(jié)點(diǎn)抽一個(gè)結(jié)點(diǎn)的索引構(gòu)建方法，可以減少了一半的索引結(jié)點(diǎn)存儲(chǔ)空間。

實(shí)際上，在軟件開(kāi)發(fā)中，我們不必太在意索引占用的額外空間。在講數(shù)據(jù)結(jié)構(gòu)的時(shí)候，我們習(xí)慣性地把要處理的數(shù)據(jù)看成整數(shù)，但是在實(shí)際的軟件開(kāi)發(fā)中，原始鏈表中存儲(chǔ)的有可能是很大的對(duì)象，而索引結(jié)點(diǎn)只需要存儲(chǔ)關(guān)鍵值和幾個(gè)指針，并不需要存儲(chǔ)對(duì)象，所以當(dāng)對(duì)象比索引結(jié)點(diǎn)大很多時(shí)，那索引占用的額外空間就可以忽略了。

5、跳表的插入
跳表插入的時(shí)間復(fù)雜度為：O(logn)，支持高效的動(dòng)態(tài)插入。

在單鏈表中，一旦定位好要插入的位置，插入結(jié)點(diǎn)的時(shí)間復(fù)雜度是很低的，就是O(1)。但是為了保證原始鏈表中數(shù)據(jù)的有序性，我們需要先找到要插入的位置，這個(gè)查找的操作就會(huì)比較耗時(shí)。

對(duì)于純粹的單鏈表，需要遍歷每個(gè)結(jié)點(diǎn)，來(lái)找到插入的位置。但是對(duì)于跳表來(lái)說(shuō)，查找的時(shí)間復(fù)雜度為O(logn)，所以這里查找某個(gè)數(shù)據(jù)應(yīng)該插入的位置的時(shí)間復(fù)雜度也是O(logn)，如下圖所示：

image.png

6、跳表的刪除
跳表的刪除操作時(shí)間復(fù)雜度為：O(logn)，支持動(dòng)態(tài)的刪除。

在跳表中刪除某個(gè)結(jié)點(diǎn)時(shí)，如果這個(gè)結(jié)點(diǎn)在索引中也出現(xiàn)了，我們除了要?jiǎng)h除原始鏈表中的結(jié)點(diǎn)，還要?jiǎng)h除索引中的。因?yàn)閱捂湵碇械膭h除操作需要拿到刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后再通過(guò)指針操作完成刪除。所以在查找要?jiǎng)h除的結(jié)點(diǎn)的時(shí)候，一定要獲取前驅(qū)結(jié)點(diǎn)（雙向鏈表除外）。因此跳表的刪除操作時(shí)間復(fù)雜度即為O(logn)。

7、跳表索引動(dòng)態(tài)更新
當(dāng)我們不斷地往跳表中插入數(shù)據(jù)時(shí)，我們?nèi)绻桓滤饕?，就有可能出現(xiàn)某2個(gè)索引節(jié)點(diǎn)之間的數(shù)據(jù)非常多的情況，在極端情況下，跳表還會(huì)退化成單鏈表，如下圖所示：

image.png

作為一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，我們需要某種手段來(lái)維護(hù)索引與原始鏈表大小之間的平衡，也就是說(shuō)，如果鏈表中的結(jié)點(diǎn)多了，索引結(jié)點(diǎn)就相應(yīng)地增加一些，避免復(fù)雜度退化，以及查找、插入和刪除操作性能的下降。

如果你了解紅黑樹(shù)、AVL樹(shù)這樣的平衡二叉樹(shù)，你就會(huì)知道它們是通過(guò)左右旋的方式保持左右子樹(shù)的大小平衡，而跳表是通過(guò)隨機(jī)函數(shù)來(lái)維護(hù)“平衡性”。

當(dāng)我們往跳表中插入數(shù)據(jù)的時(shí)候，我們可以通過(guò)一個(gè)隨機(jī)函數(shù)，來(lái)決定這個(gè)結(jié)點(diǎn)插入到哪幾級(jí)索引層中，比如隨機(jī)函數(shù)生成了值K，那我們就將這個(gè)結(jié)點(diǎn)添加到第一級(jí)到第K級(jí)這個(gè)K級(jí)索引中。如下圖中要插入數(shù)據(jù)為6，K=2的例子：

image.png

隨機(jī)函數(shù)的選擇是非常有講究的，從概率上講，能夠保證跳表的索引大小和數(shù)據(jù)大小平衡性，不至于性能的過(guò)度退化。至于隨機(jī)函數(shù)的選擇，見(jiàn)下面的代碼實(shí)現(xiàn)過(guò)程，而且實(shí)現(xiàn)過(guò)程并不是重點(diǎn)，掌握思想即可。

8、跳表的性質(zhì)
(1) 由很多層結(jié)構(gòu)組成，level是通過(guò)一定的概率隨機(jī)產(chǎn)生的；
(2) 每一層都是一個(gè)有序的鏈表，默認(rèn)是升序；
(3) 最底層(Level 1)的鏈表包含所有元素；
(4) 如果一個(gè)元素出現(xiàn)在Level i 的鏈表中，則它在Level i 之下的鏈表也都會(huì)出現(xiàn)；
(5) 每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向同一鏈表中的下一個(gè)元素，一個(gè)指向下面一層的元素。

平民版跳表實(shí)現(xiàn)，若果你對(duì)跳表實(shí)現(xiàn)完全沒(méi)概念，可一觀

skip_list_test.go

package skip_list_2

import (
    "testing"
)

func TestNewSkipList(t *testing.T) {
    root := NewLinkedList()
    data := []int{1, 3, 4, 5, 7, 8, 9, 10, 13, 16, 17, 18}
    for i := range data {
        root.InsertToTail(data[i])
    }
    skipList := NewSkipList(4, root)
    skipList.Dump()
    skipList.search(1)
    skipList.insert(6)
    skipList.Dump()

    skipList.search(6)

}

skip_list.go

package skip_list_2

import (
    "fmt"
    "math/rand"
)

type SkipList struct {
    maxHeight int
    root      *LinkedList
    indexList []*LinkedList
    step      int
}

func NewSkipList(step int, root *LinkedList) *SkipList {
    skipList := &SkipList{root: root, step: step}
    skipList.createIndexList()
    return skipList

}

func (sl *SkipList) isEmpty() bool {
    return sl.root.length == 0
}

func (sl *SkipList) createIndexList() {
    sl.indexList = make([]*LinkedList, 0, 0)
    var currentList *LinkedList
    for {
        if currentList == nil {
            currentList = sl.root
        }

        tmpList := NewLinkedList()
        for i := 0; i < currentList.length; i += sl.step {

            if i == 0 {
                node := currentList.FindByIndex(i)
                newNode := tmpList.InsertToTail(node.value)
                newNode.down = node
            } else {
                node := currentList.FindByIndex(i)
                newNode := tmpList.InsertToTail(node.value)
                newNode.down = node
            }
        }
        if tmpList.length == 1 { // 只有一個(gè)索引，沒(méi)有什么意義
            break
        }
        sl.indexList = append(sl.indexList, tmpList)
        fmt.Println(tmpList)
        if tmpList.length == 2 { //最頂層只有三個(gè)索引
            break
        } else {
            currentList = tmpList
        }

    }
}

func (sl *SkipList) search(v int) *Node {
    fmt.Println("----- search start-----", v)
    list := sl.indexList[len(sl.indexList)-1]
    var tNode *Node
    tNode = list.FindByIndex(0)
    fmt.Println(tNode)
    for {
        var nodeL, nodeR *Node
        nodeL = tNode
        nodeR = tNode.next
        fmt.Printf("左節(jié)點(diǎn)%v -->> 右節(jié)點(diǎn)%v\n", nodeL, nodeR)
        if nodeR == nil { // 當(dāng)前層， nodeL 就是最后一個(gè)點(diǎn)
            tNode = nodeL.down
        } else if v >= nodeL.value && v < nodeR.value {
            tNode = nodeL.down
        } else if v >= nodeR.value {
            tNode = nodeR.down
        }
        if tNode.down == nil {
            break
        }
        if tNode.next == nil {
            tNode = tNode.down
        }
    }
    fmt.Printf("原始節(jié)點(diǎn)%v\n", tNode)
    for {
        if tNode == nil || tNode.value > v {
            fmt.Println("找不到對(duì)應(yīng)的node")
            return nil
        }
        if tNode.value == v {
            fmt.Println("找到了node", tNode)
            return tNode
        }
        fmt.Println("繼續(xù)查找node")
        tNode = tNode.next
    }

}

func (sl *SkipList) searchPer(v int) *Node {
    fmt.Println("----- searchPer start-----", v)
    list := sl.indexList[len(sl.indexList)-1]
    var tNode *Node
    tNode = list.FindByIndex(0)
    fmt.Println(tNode)
    for {
        var nodeL, nodeR *Node
        nodeL = tNode
        nodeR = tNode.next
        fmt.Printf("左節(jié)點(diǎn)%v -->> 右節(jié)點(diǎn)%v\n", nodeL, nodeR)
        if nodeR == nil { // 當(dāng)前層， nodeL 就是最后一個(gè)點(diǎn)
            tNode = nodeL.down
        } else if v >= nodeL.value && v < nodeR.value {
            tNode = nodeL.down
        } else if v >= nodeR.value {
            tNode = nodeR.down
        }
        if tNode.down == nil {
            break
        }
        if tNode.next == nil {
            tNode = tNode.down
        }
    }
    fmt.Printf("原始節(jié)點(diǎn)%v\n", tNode)
    for {
        if tNode.next == nil {
            fmt.Println("找到了要插入的節(jié)點(diǎn)", tNode)
            return tNode
        }

        if tNode.next.value >= v {
            fmt.Println("找到了要插入的節(jié)點(diǎn)", tNode)
            return tNode
        }

        fmt.Println("繼續(xù)查找node")
        tNode = tNode.next
    }
}
func (sl *SkipList) insert(v int) bool {
    fmt.Println("----- insert start-----", v)
    node := sl.searchPer(v)
    tmp := node.next
    node.next = NewNode(v)
    node.next.next = tmp

    //插入完成后 更新索引

    level := rand.Intn(len(sl.indexList))
    fmt.Println("隨機(jī)索引層為: ", level)
    insertNode := NewNode(v)
    for l := level; l >= 0; l-- {
        // 確認(rèn)插入位置的
        node := sl.indexList[l].FindByIndex(0)
        var target *Node
        for {
            nodeL := node
            nodeR := node.next
            if nodeR == nil {
                target = nodeL
                break
            } else if v >= nodeL.value && v < nodeR.value {
                target = nodeL
                break
            } else if v >= nodeR.value {
                target = nodeR
                break
            }
            node = node.next
        }
        tmp := target.next
        target.next = insertNode
        insertNode.next = tmp

        newInsertNode := NewNode(v)
        insertNode.down = newInsertNode
        insertNode = newInsertNode
    }

    return true
}

func (sl *SkipList) Dump() {
    fmt.Println("----- dump start-----")

    for i := len(sl.indexList) - 1; i >= 0; i-- {
        sl.indexList[i].Print()
    }
    sl.root.Print()
    fmt.Println("----- dump end-----")

}

linked_list.go

package skip_list_2

import "fmt"

type Node struct {
    next  *Node
    value int
    down  *Node
}

type LinkedList struct {
    head   *Node
    length int
}

func NewNode(v int) *Node {
    return &Node{nil, v, nil}
}

func (this *Node) GetNext() *Node {
    return this.next
}

func (this *Node) GetValue() int {
    return this.value
}

func NewLinkedList() *LinkedList {
    return &LinkedList{NewNode(0), 0}
}

//在某個(gè)節(jié)點(diǎn)后面插入節(jié)點(diǎn)
func (this *LinkedList) InsertAfter(p *Node, v int) *Node {
    if nil == p {
        return nil
    }
    newNode := NewNode(v)
    oldNext := p.next
    p.next = newNode
    newNode.next = oldNext
    this.length++
    return newNode
}

//在某個(gè)節(jié)點(diǎn)前面插入節(jié)點(diǎn)
func (this *LinkedList) InsertBefore(p *Node, v int) bool {
    if nil == p || p == this.head {
        return false
    }
    cur := this.head.next
    pre := this.head
    for nil != cur {
        if cur == p {
            break
        }
        pre = cur
        cur = cur.next
    }
    if nil == cur {
        return false
    }
    newNode := NewNode(v)
    pre.next = newNode
    newNode.next = cur
    this.length++
    return true
}

//在鏈表頭部插入節(jié)點(diǎn)
func (this *LinkedList) InsertToHead(v int) *Node {
    return this.InsertAfter(this.head, v)
}

//在鏈表尾部插入節(jié)點(diǎn)
func (this *LinkedList) InsertToTail(v int) *Node {
    cur := this.head
    for nil != cur.next {
        cur = cur.next
    }
    return this.InsertAfter(cur, v)
}

//通過(guò)索引查找節(jié)點(diǎn)
func (this *LinkedList) FindByIndex(index int) *Node {
    if index >= this.length {
        return nil
    }
    cur := this.head.next
    var i int = 0
    for ; i < index; i++ {
        cur = cur.next
    }
    return cur
}

//刪除傳入的節(jié)點(diǎn)
func (this *LinkedList) DeleteNode(p *Node) bool {
    if nil == p {
        return false
    }
    cur := this.head.next
    pre := this.head
    for nil != cur {
        if cur == p {
            break
        }
        pre = cur
        cur = cur.next
    }
    if nil == cur {
        return false
    }
    pre.next = p.next
    p = nil
    this.length--
    return true
}

//打印鏈表
func (this *LinkedList) Print() {
    cur := this.head.next
    format := ""
    for nil != cur {
        format += fmt.Sprintf("%+v", cur.GetValue())
        cur = cur.next
        if nil != cur {
            format += "->"
        }
    }
    fmt.Println(format)
}

/*
單鏈表反轉(zhuǎn)
時(shí)間復(fù)雜度：O(N)
*/
func (this *LinkedList) Reverse() {
    if nil == this.head || nil == this.head.next || nil == this.head.next.next {
        return
    }

    var pre *Node = nil
    cur := this.head.next
    for nil != cur {
        tmp := cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    }

    this.head.next = pre
}

/*
判斷單鏈表是否有環(huán)
*/
func (this *LinkedList) HasCycle() bool {
    if nil != this.head {
        slow := this.head
        fast := this.head
        for nil != fast && nil != fast.next {
            slow = slow.next
            fast = fast.next.next
            if slow == fast {
                return true
            }
        }
    }
    return false
}

/*
刪除倒數(shù)第N個(gè)節(jié)點(diǎn)
*/
func (this *LinkedList) DeleteBottomN(n int) {
    if n <= 0 || nil == this.head || nil == this.head.next {
        return
    }

    fast := this.head
    for i := 1; i <= n && fast != nil; i++ {
        fast = fast.next
    }

    if nil == fast {
        return
    }

    slow := this.head
    for nil != fast.next {
        slow = slow.next
        fast = fast.next
    }
    slow.next = slow.next.next
}

/*
獲取中間節(jié)點(diǎn)
*/
func (this *LinkedList) FindMiddleNode() *Node {
    if nil == this.head || nil == this.head.next {
        return nil
    }
    if nil == this.head.next.next {
        return this.head.next
    }

    slow, fast := this.head, this.head
    for nil != fast && nil != fast.next {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}

func main() {
    list := NewLinkedList()
    list.InsertToTail(2)
    list.InsertToHead(1)
    list.InsertToTail(3)
    list.InsertToTail(4)
    list.Reverse()
    list.Print()
    if list.HasCycle() {
        fmt.Println("has cycle")
    }
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

跳表

跳表

跳表的定義

跳表的詳解

跳表的時(shí)間復(fù)雜度

跳表的空間復(fù)雜度

平民版跳表實(shí)現(xiàn)，若果你對(duì)跳表實(shí)現(xiàn)完全沒(méi)概念，可一觀

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

跳表

跳表的定義

跳表的詳解

跳表的時(shí)間復(fù)雜度

跳表的空間復(fù)雜度

平民版跳表實(shí)現(xiàn)，若果你對(duì)跳表實(shí)現(xiàn)完全沒(méi)概念，可一觀

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

平民版跳表實(shí)現(xiàn)，若果你對(duì)跳表實(shí)現(xiàn)完全沒(méi)概念，可一觀