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

package main
import . "nc_tools"

func isPail( head *ListNode ) bool {
    if head == nil || head.Next == nil {
        return true
    }

    //1，找链表中点，双数就是后面的数
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }

    //2，翻转链表
    var pre *ListNode
    cur := slow
    for cur != nil {
        temp := cur.Next
        cur.Next = pre
        pre = cur
        cur = temp
    }

    //3，比较链表值大小
    mid := pre
    for mid != nil {
        if mid.Val != head.Val {
            return false
        }
        mid = mid.Next
        head = head.Next
    }
    return true
}