線性表的鏈?zhǔn)酱鎯Γ约笆褂每炻羔樥也恢L度鏈表的中間節(jié)點(diǎn)

題目描述

首先，給定一個(gè)帶有頭結(jié)點(diǎn) head 的不知長度鏈表，返回鏈表的中間結(jié)點(diǎn)。
如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)中間結(jié)點(diǎn)。注意鏈表長度未知，這里測試定義的鏈表結(jié)構(gòu)體存儲的數(shù)據(jù)類型可以用字符串類型。
示例說明：
實(shí)例1
輸入：“one”-"two"-"three"-"four"-"five"
輸出：鏈表的中間節(jié)點(diǎn)為 ["three"]
實(shí)例2
輸入：“tom”-"jack"-"kaka"-"James"-"vickor"-"wade"-"aha"-"tiger"
輸出：鏈表的中間節(jié)點(diǎn)為 ["James","vickor"]

解題思路

設(shè)置兩個(gè)指針，一個(gè)快指針，每次走兩步，一個(gè)慢指針，每次走一步，當(dāng)快指針為空(偶數(shù)個(gè)節(jié)點(diǎn))或者快指針的next指針指向空時(shí)(奇數(shù)個(gè)節(jié)點(diǎn))，此時(shí)慢指針即為中間節(jié)點(diǎn)。
步驟：
首先定義線性表的鏈?zhǔn)酱鎯?，單個(gè)節(jié)點(diǎn)的定義如下
type Node struct { // 定義一個(gè)node結(jié)構(gòu)體
data string
next *Node
}
緊接著定義相應(yīng)的方法，主要有增加節(jié)點(diǎn)Append、獲取長度GetLength、獲取中間節(jié)點(diǎn)GetCenterNode等。
在鏈表尾部增加節(jié)點(diǎn)：
func (n *Node) Append(data string){
createNode := &Node{data,nil}
for n.next != nil{
n = n.next
}
n.next = createNode
}
獲取整個(gè)鏈表的長度：
func (n *Node) GetLength() int{
if n.next==nil{
return 0
}
length:= 0
for n.next!=nil{
length ++
n = n.next
}
return length
}
獲取整個(gè)鏈表中間節(jié)點(diǎn)：（這里有對不同情況分別討論，如一些邊界條件、鏈表長度為奇數(shù)偶數(shù)時(shí)分別討論）
func (n Node)GetCenterNode()[]string{
str := make([]string,0,2)
if n.next==nil{
return nil
}
l := n.next
s := n.next
for s.next!= nil{
// 單數(shù)情況
if l.next==nil{
str = append(str, s.data)
return str
}
// 雙數(shù)情況
if l.next != nil && l.next.next == nil{
str = append(str,s.data)
str = append(str,s.next.data)
return str
}
s =s.next
l = l.next.next
}
return str
}
首先初始化一個(gè)鏈表
// 初始化一個(gè)鏈表
func initLinkList ()Node{
return &Node{"genesis node", nil}
}
通過隨機(jī)數(shù)拼接生成一個(gè)長度為20的隨機(jī)鏈表，用于測試
func Rand20List(n *Node){
for i:=0;i<3;i++{
n.Append("this is "+strconv.Itoa(i))
}
}
通過main函數(shù)進(jìn)行測試，當(dāng)然也可通過寫測試函數(shù)進(jìn)行測試。
func main(){
link := initLinkList()
var s int
for {
fmt.Println("1.查看鏈表")
fmt.Println("2.創(chuàng)建鏈表20個(gè)數(shù)據(jù)")
fmt.Println("3.鏈表長度")
fmt.Println("4.查看中間節(jié)點(diǎn)值")
fmt.Println("5.退出")
fmt.Println("請輸入選擇：")
fmt.Scan(&s)
switch s {
case 1:
fmt.Println(link.MapLinkList())
case 2:
Rand20List(link)
case 3:
fmt.Println(link.GetLength())
case 4:
fmt.Println(link.GetCenterNode())
case 5:
return
}
}
}

完整代碼

完整線性表的鏈?zhǔn)酱鎯?，以及使用快慢指針找不知長度鏈表的中間節(jié)點(diǎn)代碼如下：

package main
import (
    "fmt"
    "strconv"
)
// 定義一個(gè)node結(jié)構(gòu)體
type Node struct {
    data string
    next *Node
}
func (n *Node) Append(data string){
    createNode := &Node{data,nil}
    for n.next != nil{
        n = n.next
    }
    n.next = createNode
}
func (n *Node) GetLength() int{
    if n.next==nil{
        return 0
    }
    length:= 0
    for n.next!=nil{
        length ++
        n = n.next
    }
    return length
}
func (n *Node) MapLinkList()[]string{
    var str []string
    if n.next == nil{
        return nil
    }
    for n.next != nil{
        str = append(str,n.next.data)
        n = n.next
    }
    return str
}
// 快慢指針法求不知道長度的鏈表的中間值
func (n *Node)GetCenterNode()[]string{
    str := make([]string,0,2)
    if n.next==nil{
        return nil
    }
    l := n.next
    s := n.next
    for s.next!= nil{
        // 單數(shù)情況
        if l.next==nil{
             str = append(str, s.data)
             return str
        }
        // 雙數(shù)情況
        if l.next != nil && l.next.next == nil{
             str = append(str,s.data)
             str = append(str,s.next.data)
             return str
        }
        s =s.next
        l = l.next.next
    }
    return str
}
// 初始化一個(gè)鏈表
func initLinkList ()*Node{
    return &Node{"genesis node", nil}
}
func Rand20List(n *Node){
    for i:=0;i<3;i++{
        n.Append("this is "+strconv.Itoa(i))
    }
}
func main(){
    link := initLinkList()
    var s int
    for {
        fmt.Println("1.查看鏈表")
        fmt.Println("2.創(chuàng)建鏈表20個(gè)數(shù)據(jù)")
        fmt.Println("3.鏈表長度")
        fmt.Println("4.查看中間節(jié)點(diǎn)值")
        fmt.Println("5.退出")
        fmt.Println("請輸入選擇：")
        fmt.Scan(&s)
        switch s {
        case 1:
            fmt.Println(link.MapLinkList())
        case 2:
            Rand20List(link)
        case 3:
            fmt.Println(link.GetLength())
        case 4:
            fmt.Println(link.GetCenterNode())
        case 5:
            return
        }
    }
}

最后，通往北京的路有很多條，你也可以有其他更好的方法，歡迎一起交流學(xué)習(xí)，共同進(jìn)步。