yankewei
commented
4 years ago 双指针
挺简单的，找到链表的中间位置，然后把右边的链表翻转，和左边的链表对比即可。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
if head == nil {
return true
}
dummy := head
s,f := head, head
for f.Next != nil && f.Next.Next != nil {
f = f.Next.Next
s = s.Next
}
reverseList := reverse(s.Next)
s.Next = nil
for dummy != nil && reverseList != nil {
if dummy.Val != reverseList.Val {
return false
}
dummy = dummy.Next
reverseList = reverseList.Next
}
return true
}
// 翻转链表
func reverse(head *ListNode) *ListNode {
var ret *ListNode
for head != nil {
next := head.Next
head.Next = ret
ret = head
head = next
}
return ret
}
请判断一个链表是否为回文链表。
示例 1:
示例 2:
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。