70 - 回文链表

题目

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

示例 1:

输入: 1->2 输出: false

示例 2:

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

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

解答

作者：reedfan

链接：https://leetcode-cn.com/problems/palindrome-linked-list/solution/ji-bai-liao-bai-fen-zhi-97de-javayong-hu-by-reedfa/

思路是把链表从中截断，前半部分翻转，然后一个个比较是否一样。

那么怎么跑到中间呢？方法是设两个快慢指针，快指针速度是慢指针两倍，这样快指针到头的时候，慢指针就正好在中间。

var isPalindrome = function (head) {
  if (!head || !head.next) {
    return true
  }

  // 快慢指针
  let fast = head.next.next
  slow = head.next
  while (fast && fast.next) {
    fast = fast.next.next
    slow = slow.next
  }

  // 翻转前半部分链表
  let pre = null
  next = null
  while (head != slow) {
    next = head.next
    head.next = pre
    pre = head
    head = next
  }

  if (fast) {
    slow = slow.next
  }
  // 回文校验
  while (pre) {
    if (pre.val != slow.val) {
      return false
    }
    pre = pre.next
    slow = slow.next
  }
  return true
};

Runtime: 56 ms, faster than 93.41% of JavaScript online submissions for Palindrome Linked List.

Memory Usage: 39.5 MB, less than 86.67% of JavaScript online submissions for Palindrome Linked List.

不过快慢指针在走的时候，其实前半部分就能顺便翻转掉了：

var isPalindrome = function (head) {
  if (!head || !head.next) {
    return true
  }

  // 快慢指针
  let pre = null
  next = null
  fast = head
  slow = head
  while (fast && fast.next) {
    fast = fast.next.next
    pre = slow
    slow = slow.next
    pre.next = next
    next = pre
  }

  if (fast) {
    slow = slow.next
  }
  // 回文校验
  while (pre) {
    if (pre.val != slow.val) {
      return false
    }
    pre = pre.next
    slow = slow.next
  }
  return true
};

Runtime: 60 ms, faster than 82.97% of JavaScript online submissions for Palindrome Linked List.

Memory Usage: 39.5 MB, less than 86.67% of JavaScript online submissions for Palindrome Linked List.

func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }

    var pre *ListNode
    var next *ListNode
    fast := head
    slow := head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        pre = slow
        slow = slow.Next
        pre.Next = next
        next = pre
    }

    if fast != nil {
        slow = slow.Next
    }
    for pre != nil {
        if pre.Val != slow.Val {
            return false
        }
        pre = pre.Next
        slow = slow.Next
    }
    return true
}

Runtime: 12 ms, faster than 92.63% of Go online submissions forPalindrome Linked List.

Memory Usage: 6.1 MB, less than 50.00% of Go online submissions forPalindrome Linked List.