234.回文链表 👌

234. 回文链表

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

方法一：快慢指针

避免使用 O(n)额外空间的方法就是改变输入。
我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。
该方法虽然可以将空间复杂度降到 O(1)，但是在并发环境下，该方法也有缺点。在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。
算法
整个流程可以分为以下五个步骤：

1. 找到前半部分链表的尾节点。
2. 反转后半部分链表。
3. 判断是否回文。
4. 恢复链表。
5. 返回结果。

执行步骤一，我们可以计算链表节点的数量，然后遍历链表找到前半部分的尾节点。
我们也可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
若链表有奇数个节点，则中间的节点应该看作是前半部分。
步骤二可以使用「206. 反转链表」问题中的解决方法来反转链表的后半部分。
步骤三比较两个部分的值，当后半部分到达末尾则比较完成，可以忽略计数情况中的中间节点。
步骤四与步骤二使用的函数相同，再反转一次恢复链表本身。

//快慢指针，先找到中间节点，再反转后链表，因为就算是奇数，前链表的中间.Next还是指向mid
func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }
    //找链表中点，偶数为中点的后数，返回中点slow
    slow ,fast := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    //翻转后链表，从slow开始,返回新的cur链表
    var pre *ListNode
    cur := slow
    for cur != nil {
        temp := cur.Next
        cur.Next = pre
        pre = cur
        cur = temp
    }
    //遍历链表值，比较相等,后链表和全链表的一半比
    mid := pre
    for mid != nil {
        if head.Val != mid.Val {
            return false
        }
        mid = mid.Next
        head =head.Next
    }
    return true
}

复杂度分析

• 时间复杂度：O(n)，其中 nn 指的是链表的元素个数。
  • 第一步： 遍历链表并将值复制到数组中，O(n)。
  • 第二步：双指针判断是否为回文，执行了 O(n/2) 次的判断，即 O(n)。
  • 总的时间复杂度：O(2n) =O(n)。

• 空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。

  //哈希表法？
  func isPalindrome(head *ListNode) bool {
    vals := []int{}                 //创建一个数组用于存值
    for  ; head != nil ;head = head.Next {
        vals = append(vals,head.Val)
    }
  
    n := len(vals)
    for i ,v := range vals[:n/2] {  // 5/2=2 整除
        if v != vals[n-1-i] {       // 5-1-2=2 后面逼近
            return false
        }
    }
    return true
  }