234. 回文链表

题目描述：

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

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路:

第一种简单的思路是遍历一遍，将数据保存在数组里面，然后从两边开始遍历

第二种是进阶算法，用快慢指针，一个指针一次走两步，一个一次走一步，然后快指针走完慢指针刚刚走到一半，将后半链表逆置，然后前半链表和后半比较

代码:

func isPalindrome(head *ListNode) bool {
    if head.Next==nil||head==nil{
        return true
    }
    var pre *ListNode=nil
    fast,slow :=head,head
    for fast!=nil&&fast.Next!=nil{
        fast=fast.Next.Next
        pre=slow
        slow=slow.Next
    }
    pre.Next=nil
//翻转链表
var head2 *ListNode=nil
for(slow!=nil){
    tmp:=slow.Next
    slow.Next=head2
    head2=slow
    slow=tmp
}
    for head!=nil{
            if head2.Val!=head.Val{
                return false
            }else{
                head=head.Next
                head2=head2.Next
            }
    }
    return true
}

代码效率：

执行用时：172 ms, 在所有 Go 提交中击败了23.75%的用户
内存消耗：9.3 MB, 在所有 Go 提交中击败了29.47%的用户