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

func isPail( head *ListNode ) bool {
    // write code here
    if head == nil || head.Next == nil {
        return true 
    }
    
    part1 := head 
    part2 := CutList(head)
    part2 = Reverse(part2)
    
    for part1 != nil && part2 != nil {
        if part1.Val != part2.Val {
            return false 
        }
        part1 = part1.Next
        part2 = part2.Next
    }
    
    return true 
}

func Reverse(head *ListNode) *ListNode {
    var prev, next *ListNode 
    for head != nil {
        next = head.Next
        head.Next = prev 
        prev = head 
        head = next
    }
    
    return prev 
}

func CutList(head *ListNode) *ListNode {
    dummy := &ListNode{0, head}
    fast := dummy 
    slow := dummy 
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    
    tmp := slow.Next
    slow.Next = nil 
    
    return tmp 
}