赞
踩
题目:
题解:
- func reverseList(head *ListNode) *ListNode {
- var prev, cur *ListNode = nil, head
- for cur != nil {
- nextTmp := cur.Next
- cur.Next = prev
- prev = cur
- cur = nextTmp
- }
- return prev
- }
-
- func endOfFirstHalf(head *ListNode) *ListNode {
- fast := head
- slow := head
- for fast.Next != nil && fast.Next.Next != nil {
- fast = fast.Next.Next
- slow = slow.Next
- }
- return slow
- }
-
- func isPalindrome(head *ListNode) bool {
- if head == nil {
- return true
- }
-
- // 找到前半部分链表的尾节点并反转后半部分链表
- firstHalfEnd := endOfFirstHalf(head)
- secondHalfStart := reverseList(firstHalfEnd.Next)
-
- // 判断是否回文
- p1 := head
- p2 := secondHalfStart
- result := true
- for result && p2 != nil {
- if p1.Val != p2.Val {
- result = false
- }
- p1 = p1.Next
- p2 = p2.Next
- }
-
- // 还原链表并返回结果
- firstHalfEnd.Next = reverseList(secondHalfStart)
- return result
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。