回文链表-简单

难度：简单

题目描述：
请判断一个链表是否为回文链表。

示例：

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

1
2

解题思路：
循环读数然后头尾对比 ```javascript var isPalindrome = function(head) { let arr = []; let cur = head; while (cur) { arr.push(cur); cur = cur.next; } console.log(arr); let i = 0; let j = arr.length - 1; let state = true; while (i < j) { if (arr[i].val !== arr[j].val) { state = false; } i++; j--; } return state; }; ```

只要找到链表的中间位置，以中间位置为分界线，反转前半部分，再用反转了的前半部分与后半部分做对比，如有不同就返回 false。
这一种做法虽然有两次遍历，但两次遍历的长度均为链表个数的一半，所以达到时间复杂度为 O(n)O(n)

var isPalindrome = function (head) {
  if (head === null || head.next === null) return true;
  let mid = head;
  let pre = null;
  let reversed = null;
  // end每次走两格，这个循环的时间复杂度为O(n/2)
  while (head !== null && head.next !== null) {
    // 这个赋值要在mid被修改前提前
    pre = mid;
    // 遍历链表
    mid = mid.next;
    head = head.next.next;
    // 反转前面部分的节点，并用reversed保存
    pre.next = reversed;
    reversed = pre;
  }
  // 奇数mid往后走一位
  if (head) mid = mid.next;
  while (mid) {
    if (reversed.val !== mid.val) return false;
    reversed = reversed.next;
    mid = mid.next;
  }
  return true;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

← 反转链表-简单移除链表元素-简单 →

# 回文链表-简单

回文链表-简单