题解 | #判断一个链表是否为回文结构#

package main

import (
	. "nc_tools"

)

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类 the head
 * @return bool布尔型
 */
func isPail(head *ListNode) bool {
	// 1、通过快慢指针确定后半部分链表位置
	// 2、反转后半部分链表
	// 3、已后半部分链表为标准，比对
	if head == nil {
		return false
	}
	if head.Next == nil {
		return true
	}

	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	slow.Next = reverseList(slow.Next)
	slow = slow.Next
	p1, p2 := head, slow
	reslut := true
	for reslut && p2 != nil {
		if p1.Val != p2.Val {
			return false
		}
		p1 = p1.Next
		p2 = p2.Next
	}
	return reslut
}

func reverseList(head *ListNode) *ListNode {
	var prev *ListNode = nil
	curr := head
	for curr != nil {
		temp := curr.Next
		curr.Next = prev
		prev = curr
		curr = temp
	}
	return prev

}