(链表)回文链表

原题：234. 回文链表 - 力扣（LeetCode） (leetcode-cn.com)

思路：我们利用两个指针，一个快指针，一个慢指针，快指针移动速度为两倍，当快指针到底的时候慢指针在中间（需要根据奇偶来进行判断），这个时候我们只需要反转慢指针后面的链表，最后比对两个链表就可以了

// 自己定义的链表
type ListNode struct {
	Val int
	Next *ListNode
}

// 链表反转 这个之前详细介绍过
func reverse(head *ListNode) *ListNode {
	var pre,cur *ListNode
	pre,cur = nil,head
	for cur !=nil{
		next:= cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}


// 判断是否为回文字符串
func isPalindrome(head *ListNode) bool {
	// 定义一个块指针，一个慢指针
	slow:=head
	fast:=head

	// 进行遍历让快指针到达程序结尾
	for fast!=nil && fast.Next!=nil{
		slow = slow.Next
		// 快指针以两倍的速度进行移动
		fast = fast.Next.Next
	}

	// 当快指针转移到最结尾的时候,如果不是空，就说明是奇数情况，这时候慢指针需要向左移
	if fast != nil{
		slow = slow.Next
	}

	// 下面我们需要对后半部分链表进行反转
	left:=head
	right:=reverse(slow)

	// 开始进行判断
	for right!=nil{
		if left.Val != right.Val {
			return false
		}
		left = left.Next
		right = right.Next
	}

	return true
}


func main()  {
	node:=new(ListNode)
	first:=node
	node.Val = 1
	node.Next = new(ListNode)
	node=node.Next
	node.Val = 2
	node.Next = new(ListNode)
	node=node.Next
	node.Val = 3
	node.Next = new(ListNode)
	node=node.Next
	node.Val = 2
	node.Next = new(ListNode)
	node=node.Next
	node.Val = 2
	fmt.Println(isPalindrome(first))
}