234. 回文链表

[yankewei]

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[yankewei]

双指针

挺简单的，找到链表的中间位置，然后把右边的链表翻转，和左边的链表对比即可。

/**
 * 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
}