查找单链表中间值

问题

通过一次循环查找单链表中的中间值。

解法

常规

遍历一遍，得到单链表的长度，计算出中间值位置，再遍历一遍，遍历到中间值位置即可。

代码略。

快慢指针

用两个指针 p 和 q，开始都指向头结点。p 向后移动一位，q 向后移动两位。重复前面步骤，直到 q 到头。

如果单链表长度为奇数，q 最后可以正好到头， 此时 p 的位置即为中间值。

如果单链表长度为偶数，q 最后只能走一步到头，走不了两步。此时 p 的位置和 p.next 为中间值。

package main

import "fmt"

type Node struct {
	data int
	next *Node
}

type LinkedList struct {
	head *Node
	tail *Node
}

func (list *LinkedList) init() {
	(*list).head = nil
	(*list).tail = nil
}

func (list *LinkedList) empty() bool {
	return (*list).head == nil
}

func (list *LinkedList) append(data int) {
	node := Node{
		data: data,
		next: nil,
	}
	if (*list).head == nil {
		// 没有头部
		(*list).head = &node
		(*list).tail = &node
	} else {
		// 有头部
		(*list).tail.next = &node
		(*list).tail = &node
	}
}

func (list *LinkedList) appendMany(data ...int) {
	for _, d := range data {
		node := Node{
			data: d,
			next: nil,
		}
		if (*list).head == nil {
			(*list).head = &node
			(*list).tail = &node
		} else {
			(*list).tail.next = &node
			(*list).tail = &node
		}
	}
}

func (list *LinkedList) show() []int {
	if (*list).empty() {
		// 空链表
		return []int{}
	}
	var result []int
	p := (*list).head
	for p != nil {
		result = append(result, p.data)
		p = p.next
	}

	return result
}

func findMid(list *LinkedList) []int {
	if (*list).empty() {
		// 为空
		return []int{}
	}
	// p在后，q 在前
	p, q := (*list).head, (*list).head
	for q.next != nil {
		if q.next.next != nil {
			// 后面第二节点不为空，可以走两步
			p = p.next
			q = q.next.next
		} else {
			// 后面第二个节点为空，不能再走了，此时p和p.next为中间两个数
			return []int{p.data, p.next.data}
		}
	}
	// 此时q.next=nil，q 走到头了，p 的位置即是中间
	return []int{p.data}
}

func main() {
	var list LinkedList
	list.init()
	fmt.Printf("list: %v \n", list.show())
	fmt.Printf("list mid: %v \n\n", findMid(&list))

	list.append(2)
	fmt.Printf("list: %v \n", list.show())
	fmt.Printf("list mid: %v \n\n", findMid(&list))

	list.appendMany(2, 5, 8, 20, 21, 17)
	fmt.Printf("list: %v \n", list.show())
	fmt.Printf("list mid: %v \n\n", findMid(&list))

	list.append(9)
	fmt.Printf("list: %v \n", list.show())
	fmt.Printf("list mid: %v \n\n", findMid(&list))
}

输出：

list: []
list mid: []

list: [2]
list mid: [2]

list: [2 2 5 8 20 21 17]
list mid: [8]

list: [2 2 5 8 20 21 17 9]
list mid: [8 20]

拓展：查找倒数第n个

我们将上面的问题进行拓展，查找单链表中倒数第 n 个元素的值。

同样我们使用双指针，拉开 n-1 的距离即可。

// 获取倒数第n个元素，如果不存在返回 -1
func findNrdFromLast(list *LinkedList, n int) int {
	if n < 1 {
		return -1
	}
	if (*list).empty() {
		// 为空
		return -1
	}
	// p在后，q 在前
	p, q := (*list).head, (*list).head
	// 使 p 和 q 拉开n-1的距离
	for i := 0; i < n-1; i++ {
		if q.next != nil {
			q = q.next
		} else {
			// p 和 q 拉不开n-1 的距离，则不存在倒数第n个元素
			return -1
		}
	}
	// 同步向右移动，直到 q 到头
	for q.next != nil {
		q = q.next
		p = p.next
	}
	// q 到头了，p 的位置即是倒数第 n 个
	return p.data
}

func main() {
	var list LinkedList
	var n = 3
	list.init()
	fmt.Printf("list: %v \n", list.show())
	fmt.Printf("list last %vrd: %v \n\n", n, findNrdFromLast(&list, n))

	list.append(2)
	fmt.Printf("list: %v \n", list.show())
	fmt.Printf("list last %vrd: %v \n\n", n, findNrdFromLast(&list, n))

	list.appendMany(2, 5, 8, 20, 21, 17)
	fmt.Printf("list: %v \n", list.show())
	fmt.Printf("list last %vrd: %v \n\n", n, findNrdFromLast(&list, n))
}

输出：

list: []
list last 3rd: -1

list: [2]
list last 3rd: -1

list: [2 2 5 8 20 21 17]
list last 3rd: 20