Golang | Leetcode Golang题解之第234题回文链表
题目:
题解:
func reverseList(head *ListNode) *ListNode {var prev, cur *ListNode = nil, headfor cur != nil {nextTmp := cur.Nextcur.Next = prevprev = curcur = nextTmp}return prev
}func endOfFirstHalf(head *ListNode) *ListNode {fast := headslow := headfor fast.Next != nil && fast.Next.Next != nil {fast = fast.Next.Nextslow = slow.Next}return slow
}func isPalindrome(head *ListNode) bool {if head == nil {return true}// 找到前半部分链表的尾节点并反转后半部分链表firstHalfEnd := endOfFirstHalf(head)secondHalfStart := reverseList(firstHalfEnd.Next)// 判断是否回文p1 := headp2 := secondHalfStartresult := truefor result && p2 != nil {if p1.Val != p2.Val {result = false}p1 = p1.Nextp2 = p2.Next}// 还原链表并返回结果firstHalfEnd.Next = reverseList(secondHalfStart)return result
}