234.回文链表

[linked-list](https://leetcode.com/tag/linked-list) | [two-pointers](https://leetcode.com/tag/two-pointers)

请判断一个链表是否为回文链表。
示例 1:

输入: 1->2
输出: false

示例 2:

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

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

解法一：借助其他数据结构

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func isPalindrome(head *ListNode) bool {
    // 借助切片
    val := []int{}
    for head != nil {
        val = append(val, head.Val)
        head = head.Next
    }
    left, right := 0, len(val)-1
    // 双指针
    for left < right {
        if val[left] != val[right] {
            return false
        }
        left++
        right--
    }
    return true
}

解法二：递归

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func isPalindrome(head *ListNode) bool {
    left := head
    var traverse func(right *ListNode) bool
    traverse = func(right *ListNode) bool {
        if right == nil {
            return true
        }
        // res 递归结束时，right 是最右边的节点也就是最后一个节点
        res := traverse(right.Next)
        res = res && (right.Val == left.Val)
        left = left.Next
        return res
    }
    return traverse(head)
}

解法三：快慢指针

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func isPalindrome(head *ListNode) bool {
    slow, fast := head, head
    prev := head
    for fast != nil && fast.Next != nil {
        prev = slow
        slow = slow.Next
        fast = fast.Next.Next
    }
    // 分隔链表
    prev.Next = nil

    // 反转剩下的节点
    head2 := reverse(slow)
    // 链表不确定奇偶性，head2 >= head1，所以只需要判断 head 即可
    for head != nil {
        if head.Val != head2.Val {
            return false
        }
        head = head.Next
        head2 = head2.Next
    }
    return true
}

func reverse(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    last := reverse(head.Next)
    head.Next.Next = head
    head.Next = nil
    return last
}