leetcode234-回文链表

leetcode 234

思路

利用快慢指针法+链表反转实现

对于链表反转的实现，在之前的博文里面有记录：链表反转
快慢指针的核心思想是找到链表的中点，把中点后面的部分进行反转，然后把后半部分反转后的链表和前半部分进行比较，如果一致则说明是回文链表

为什么利用快慢指针可以找点链表中点呢？

因为快指针走两步，慢指针走一步，快指针走的步长是慢指针的两倍，当快指针走到末尾的时候，慢指针刚好走了一半
具体步骤如下：

• 找到链表中点：使用快慢指针，快指针 fast 每次移动两步，慢指针 slow 每次移动一步。当快指针 fast 到达链表末尾或者 fast 的下一个节点为空时，慢指针 slow 正好指向链表的中点（如果链表长度为偶数，slow 指向的是前半部分的最后一个节点）
• 反转链表后半部分：从 slow 的下一个节点开始，对链表的后半部分进行反转操作。这里可以使用经典的链表反转算法，通过改变节点的指针方向实现链表反转
• 比较前后两部分：设置两个指针，一个指针 p1 指向链表头节点 head ，另一个指针 p2 指向反转后的后半部分链表的头节点。然后依次比较 p1 和 p2 指向节点的 val 值，如果在比较过程中发现不相等的值，直接返回 false ；如果能顺利比较完所有节点，则返回 true

实现

var isPalindrome = function (head) {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 反转后半部分链表
    let reverse = getReverseList(slow);
    while (reverse) {
        if (reverse.val !== head.val) {
            return false
        }
        reverse = reverse.next;
        head = head.next
    }
    return true
};

// 获取反转链表
function getReverseList(head) {
    let pre = null;
    let cur = head;
    while (cur) {
        const node = cur.next;
        cur.next = pre;
        pre = cur;
        cur = node;
    }
    return pre;
}

实现链表

一般leetcode上的题目都是给的一个数组：head = [1,2]，我们想要去调试，需要手动将这个数组转换为链表的类型，下面就是数组转链表的实现函数

export class Nodelist {
  constructor(value) {
    this.val = value;
    this.next = null
  }
}

export function getNode(arr) {
  const head = new Nodelist(arr[0])
  const len = arr.length;
  let cur = head;
  for (let i = 1; i < len; i++) {
    cur.next = new Nodelist(arr[i])
    cur = cur.next;
  }
  return head
}