题解 | #输出单向链表中倒数第k个结点#

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

// 链表结点
type Node struct {
	Value int
	Next  *Node
}

// 链表结构-包含指向第一个结点的 head 指针
type Singly struct {
	Head   *Node
	length int // 记录链表的长度
}

//  创建一个新节点
func NewNode(val int) *Node {
	return &Node{val, nil}
}

// 创建一个新链表
func NewSingly() *Singly {
	return &Singly{}
}

func (ll *Singly) AddAtEnd(val int) {
	node := NewNode(val)

	if ll.Head == nil {
		ll.Head = node
		ll.length++
		return
	}

	cur := ll.Head
	// 查找到最后一个结点
	for ; cur.Next != nil; cur = cur.Next {
	}
	cur.Next = node
	ll.length++
}

func main() {
	inputs := bufio.NewScanner(os.Stdin)
	for {
		if !inputs.Scan() {
			break
		}

		// 输入值
		inputs.Scan()
		var values []int
		for _, v := range strings.Split(inputs.Text(), " ") {
			val, _ := strconv.Atoi(v)
			values = append(values, val)
		}

		l := NewSingly()
		// 构建链表
		for _, value := range values {
			l.AddAtEnd(value)
		}

		// 读入 k
		inputs.Scan()
		k, _ := strconv.Atoi(inputs.Text())

		// 使用fast, low指针
		low := l.Head
		fast := l.Head

		// 让 fast 先走 k 个节点
		for i := 0; i < k; i++ {
			fast = fast.Next
		}

		// low 和 fast 同时开始走
		for fast != nil {
			low = low.Next
			fast = fast.Next
		}

		// 打印当前 k 的值
		fmt.Println(low.Value)
	}
}