234.回文链表

链接：234.回文链表
难度：Easy
标签：栈、递归、链表、双指针
简介：请判断一个链表是否为回文链表。

题解 1 - typescript

• 编辑时间：2020-10-23
• 执行用时：104ms
• 内存消耗：43MB
• 编程语言：typescript
• 解法介绍：快慢指针一次遍历。

function isPalindrome(head: ListNode | null): boolean {
  if (head === null) return true;
  let fast: ListNode | null = head;
  let slow: ListNode | null = head;
  const cache: number[] = [];
  while (fast !== null && fast.next !== null) {
    fast = fast.next.next;
    cache.push(slow!.val);
    slow = slow!.next;
  }
  if (fast?.next === null) slow = slow!.next;
  while (slow) {
    const val = cache.pop();
    if (slow.val !== val) return false;
    slow = slow.next;
  }
  return true;
}

题解 2 - typescript

• 编辑时间：2021-08-20
• 执行用时：260ms
• 内存消耗：66.2MB
• 编程语言：typescript
• 解法介绍：利用字符串保存翻转值。

function isPalindrome(head: ListNode): boolean {
  let str1 = '';
  let str2 = '';
  let p: ListNode | null = head;
  while (p) {
    str1 = str1 + p.val;
    str2 = p.val + str2;
    p = p.next;
  }
  return str1 === str2;
}

题解 3 - javascript

• 编辑时间：2021-09-22
• 执行用时：228ms
• 内存消耗：69.9MB
• 编程语言：javascript
• 解法介绍：反转后半部分。

function isPalindrome(head: ListNode): boolean {
        let slow = head;
        let fast = head.next;
        if (!fast) return true;
        while (fast && fast.next) {
          slow = slow.next!;
          fast = fast.next.next;
        }
        fast = reverse(slow.next!)[0];
        slow = head;
        while (fast) {
          if (slow.val !== fast.val) return false;
          slow = slow.next!;
          fast = fast.next!;
        }
        return true;
        function reverse(node: ListNode): [ListNode, ListNode] {
          if (node.next === null) return [node, node];
          const [first, last] = reverse(node.next);
          last.next = node;
          node.next = null;
          return [first, node];
        }
      }

题解 4 - javascript

• 编辑时间：2021-09-22
• 执行用时：152ms
• 内存消耗：60.7MB
• 编程语言：javascript
• 解法介绍：反转后半部分，遍历反转。

function isPalindrome(head: ListNode): boolean {
        let slow = head;
        let fast = head.next;
        if (!fast) return true;
        while (fast && fast.next) {
          slow = slow.next!;
          fast = fast.next.next;
        }
        fast = reverse(slow.next!);
        slow = head;
        while (fast) {
          if (slow.val !== fast.val) return false;
          slow = slow.next!;
          fast = fast.next!;
        }
        return true;
        function reverse(node: ListNode): ListNode {
          const head = new ListNode();
          let p: ListNode | null = node;
          while (p) {
            const oldNext = head.next;
            const next = p.next;
            head.next = p;
            p.next = oldNext;
            p = next;
          }
          return head.next!;
        }
      }

题解 5 - c

• 编辑时间：2021-11-19
• 执行用时：164ms
• 内存消耗：40.8MB
• 编程语言：c
• 解法介绍：储存数组再遍历。

bool isPalindrome(struct ListNode* head){
    int nums[100000] = {0}, len = 0;
    struct ListNode *p = head;
    while(p){
        nums[len++] = p->val;
        p = p->next;
    }
    for (int i = 0; i < len / 2; i++) {
        if (nums[i] != nums[len - 1 - i]) return 0;
    }
    return 1;
}