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

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 || head.Next == nil {
		return true
	}	
	prev,slow,fast := head,head,head
	for fast != nil && fast.Next != nil {
		prev = slow
		slow = slow.Next
		fast = fast.Next.Next
	}
	prev.Next = nil
	node := reserveList(slow)
	p1,p2 := head,node
	result := true
	for p1 != nil && p2 != nil {
		if p1.Val != p2.Val {
			result = false
			break
		}
		p1 = p1.Next
		p2 = p2.Next
	}
	return result
}


func reserveList(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	prevNode := &ListNode{}
	curr := head
	for curr != nil {
		temp := curr.Next
		curr.Next = prevNode
		prevNode = curr
		curr = temp
	}
	return prevNode
}