234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：
输入：head = [1,2,2,1]
输出：true

示例 2：
输入：head = [1,2]
输出：false

提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-linked-list

javascript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
// 解法一 反转链表
// var isPalindrome = function (head) {
//   if (head && !head.next) return true
//   var left = head
//   function reverse(right) {
//     if (!right) return true
//     var res = reverse(right.next)
//     res = res && right.val === left.val
//     left = left.next
//     return res
//   }
//   return reverse(head)
// }

// 解法二 快慢指针寻找中间点反转后部分链表
var isPalindrome = function (head) {
  if (head && !head.next) return true
  if (head && head.next && !head.next.next) return head.val === head.next.val
  var slow = head,
    fast = head

  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
  }
  console.log(slow, fast)
  if (fast) {
    slow = slow.next
  }

  var left = head,
    right = reverse(slow)

  while (right) {
    if (left.val !== right.val) {
      return false
    }
    left = left.next
    right = right.next
  }

  return true
}

function reverse(head) {
  if (!head || !head.next) return head
  var last = reverse(head.next)
  head.next.next = head
  head.next = null
  return last
}

// test
function ListNode(val, next) {
  this.val = val === undefined ? 0 : val
  this.next = next === undefined ? null : next
}

var node = new ListNode(1)
var node1 = new ListNode(2)
var node2 = new ListNode(2)
var node3 = new ListNode(1)
node.next = node1
node1.next = node2
node2.next = node3

console.log(isPalindrome(node))

234. 回文链表 #

234. 回文链表