[结构与算法的Golang实现一] 请判断一个链表是否为回文链表

结构与算法的理论知识到一段落，学了知识要落地，接下来用Golang来实现。

本文实现链表的回文字符串问题

如字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？（如level,noon）

那么单链表怎么存储字符串？

package main

import "fmt"

//***如字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？（如level,noon）***//

//那么单链表怎么存储字符串？
type StrNode struct {
	str  string
	next *StrNode //这个表示指向下一个结点
}

//给链表插入一个结点，在单链表的最后加入
func InsertStrNode(head *StrNode, newStrNode *StrNode) {
	//1.先找到最后一个结点
	//2.创建一个辅助结点
	temp := head
	for {
		//3.如果temp的next指向空，那就是最后一个结点
		if temp.next == nil {
			break
		}
		temp = temp.next //4.让temp不断指向下一个结点
	}
	//5.将newStrNode加入到链表的最后
	temp.next = newStrNode
	//fmt.Println("这就连上了")
}

//显示链表的所有结点信息
func ListStrNode(head *StrNode) {
	//1.创建一个辅助结点
	temp := head
	//2.判度该链表是不是空
	if temp.next == nil {
		fmt.Println("空链表，无法显示")
		return
	}

	//3.遍历这个链表
	for {
		fmt.Printf("[%s]=>", temp.str)
		//4.判断结点是否到链表结尾
		if temp.next == nil {
			fmt.Println("")
			break
		}
		temp = temp.next //5.指向下一个结点

	}
}

func main() {

	//a := 812565218

	//1.先创建一个头结点
	head := &StrNode{
		str: "8",
		//这里没法定义next，next要指向谁，要通过下一个结点的主动加入链表来确定，这里先空着
	}

	//2.创建新的StrNode
	str1 := &StrNode{
		str: "1",
	}
	str2 := &StrNode{
		str: "2",
	}
	str3 := &StrNode{
		str: "5",
	}
	str4 := &StrNode{
		str: "6",
	}
	str5 := &StrNode{
		str: "5",
	}
	str6 := &StrNode{
		str: "2",
	}
	str7 := &StrNode{
		str: "1",
	}
	str8 := &StrNode{
		str: "8",
	}

	//3.加入
	InsertStrNode(head, str1)
	InsertStrNode(head, str2)
	InsertStrNode(head, str3)
	InsertStrNode(head, str4)
	InsertStrNode(head, str5)
	InsertStrNode(head, str6)
	InsertStrNode(head, str7)
	InsertStrNode(head, str8)

	//4.显示
	ListStrNode(head)
}

那么怎么判断是否为回文串？

先用数组存结点的值，再前后对比

package main

import "fmt"

//***如字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？（如level,noon）***//

//那么单链表怎么存储字符串？
type StrNode struct {
	str  string
	next *StrNode //这个表示指向下一个结点
}

//给链表插入一个结点，在单链表的最后加入
func InsertStrNode(head *StrNode, newStrNode *StrNode) {
	//1.先找到最后一个结点
	//2.创建一个辅助结点
	temp := head
	for {
		//3.如果temp的next指向空，那就是最后一个结点
		if temp.next == nil {
			break
		}
		temp = temp.next //4.让temp不断指向下一个结点
	}
	//5.将newStrNode加入到链表的最后
	temp.next = newStrNode
	//fmt.Println("这就连上了")
}

//显示链表的所有结点信息
func ListStrNode(head *StrNode) {
	//1.创建一个辅助结点
	temp := head
	//2.判度该链表是不是空
	if temp.next == nil {
		fmt.Println("空链表，无法显示")
		return
	}

	//3.遍历这个链表
	for {
		fmt.Printf("[%s]=>", temp.str)
		//4.判断结点是否到链表结尾
		if temp.next == nil {
			fmt.Println("")
			break
		}
		temp = temp.next //5.指向下一个结点

	}
}

// 用数组存结点的值，前后对比
func IsPalindrome(head *StrNode) bool {
	// 空链表,算回文
	if head == nil || head.next == nil {
		return true
	}
	//1.用数组存节点的值，将链表的值一一追加到数组
	var data []string
	for temp := head; temp != nil; temp = temp.next {
		data = append(data, temp.str)
	}
	//2.前后对比。数组为偶数个时只有i<j的情况，奇数个时有i=j的情况
	for i, j := 0, len(data)-1; i <= j; {
		if data[i] != data[j] {
			return false
		}
		i++
		j--

	}

	return true
}

func main() {

	//a := 812565218

	//1.先创建一个头结点
	head := &StrNode{
		str: "8",
		//这里没法定义next，next要指向谁，要通过下一个结点的主动加入链表来确定，这里先空着
	}

	//2.创建新的StrNode
	str1 := &StrNode{
		str: "1",
	}
	str2 := &StrNode{
		str: "2",
	}
	str3 := &StrNode{
		str: "5",
	}
	str4 := &StrNode{
		str: "6",
	}
	str5 := &StrNode{
		str: "5",
	}
	str6 := &StrNode{
		str: "2",
	}
	str7 := &StrNode{
		str: "1",
	}
	str8 := &StrNode{
		str: "8",
	}

	//3.加入
	InsertStrNode(head, str1)
	InsertStrNode(head, str2)
	InsertStrNode(head, str3)
	InsertStrNode(head, str4)
	InsertStrNode(head, str5)
	InsertStrNode(head, str6)
	InsertStrNode(head, str7)
	InsertStrNode(head, str8)

	//4.显示
	ListStrNode(head)

	//5.判断
	res := IsPalindrome(head)
	fmt.Println(res)
}

这段代码的时间复杂度为O(n)，空间复杂度也为O(n)。

那么有优化方案吗？

找到链表中间节点，将前半部分转置，再从中间向左右遍历对比。
使其空间复杂度降为O(1)。

package main

import "fmt"

//***如字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？（如level,noon）***//

//那么单链表怎么存储字符串？
type StrNode struct {
	str  string
	next *StrNode //这个表示指向下一个结点
}

//给链表插入一个结点，在单链表的最后加入
func InsertStrNode(head *StrNode, newStrNode *StrNode) {
	//1.先找到最后一个结点
	//2.创建一个辅助结点
	temp := head
	for {
		//3.如果temp的next指向空，那就是最后一个结点
		if temp.next == nil {
			break
		}
		temp = temp.next //4.让temp不断指向下一个结点
	}
	//5.将newStrNode加入到链表的最后
	temp.next = newStrNode
	//fmt.Println("这就连上了")
}

//显示链表的所有结点信息
func ListStrNode(head *StrNode) {
	//1.创建一个辅助结点
	temp := head
	//2.判度该链表是不是空
	if temp.next == nil {
		fmt.Println("空链表，无法显示")
		return
	}

	//3.遍历这个链表
	for {
		fmt.Printf("[%s]=>", temp.str)
		//4.判断结点是否到链表结尾
		if temp.next == nil {
			fmt.Println("")
			break
		}
		temp = temp.next //5.指向下一个结点

	}
}

// 找到链表中间节点，将前半部分转置，再从中间向左右遍历对比
func IsPalindrome(head *StrNode) bool {
	if head == nil || head.next == nil {
		return true
	}
	res := true

	//1.链表长度
	len := 0
	for temp := head; temp != nil; temp = temp.next {
		len++
	}

	//2.将前半部分反转
	step := len / 2
	var prev *StrNode
	temp := head
	for i := 1; i <= step; i++ {
		temp.next, prev, temp = prev, temp, temp.next
	}
	mid := temp

	var left, right *StrNode = prev, nil
	if len%2 == 0 {
		//长度为偶数
		right = mid
	} else {
		right = mid.next
	}

	//3.从中间向左右两边遍历对比
	for left != nil && right != nil {
		if left.str != right.str {
			//值不相等,不是回文链表
			res = false
			break
		}
		left = left.next
		right = right.next
	}

	//4.将前半部分反转的链表进行复原
	temp = prev
	prev = mid
	for temp != nil {
		temp.next, prev, temp = prev, temp, temp.next
	}

	return res
}

func main() {

	//a := 812565218

	//1.先创建一个头结点
	head := &StrNode{
		str: "8",
		//这里没法定义next，next要指向谁，要通过下一个结点的主动加入链表来确定，这里先空着
	}

	//2.创建新的StrNode
	str1 := &StrNode{
		str: "1",
	}
	str2 := &StrNode{
		str: "2",
	}
	str3 := &StrNode{
		str: "5",
	}
	str5 := &StrNode{
		str: "5",
	}
	str6 := &StrNode{
		str: "2",
	}
	str7 := &StrNode{
		str: "1",
	}
	str8 := &StrNode{
		str: "8",
	}

	//3.加入
	InsertStrNode(head, str1)
	InsertStrNode(head, str2)
	InsertStrNode(head, str3)
	InsertStrNode(head, str5)
	InsertStrNode(head, str6)
	InsertStrNode(head, str7)
	InsertStrNode(head, str8)

	//4.显示
	ListStrNode(head)

	//5.判断
	res := IsPalindrome(head)
	fmt.Println(res)
}