leetcode 链接：回文链表
《程序员面试代码指南》by 左程云 中相同题目：★★☆☆判断一个链表是否为回文结构（进阶）

题目

编写一个函数，检查输入的链表是否是回文的。

示例：

  1. 输入： 1->2
  2. 输出： false 
  4. 输入： 1->2->2->1
  5. 输出： true 
  7. 输入： 1->2->3->2->1
  8. 输出： true

解答 & 代码

时间复杂度 O(N)，空间复杂度 O(1)

算法流程：

  • 如果链表为空或只有一个节点，直接返回 true
  • 遍历链表找到中间节点：使用双指针 slow 和 fast，初始时都指向链表第一个节点，
    • 如果 fast 的后继节点以及后继的后继节点不为 NULL，则 fast 走两步，slow 走一步
    • 否则，停止遍历，此时 slow 指向的节点就是链表中间节点

image.png

  • 将链表右半部分（中间节点 slow 之后的节点，不含 slow）逆序，将中间节点也就是左半部分链表的最后一个节点 slow 的 next 指向 NULL
  • 同时遍历左半部分链表 和 逆序后的右半部分链表
    • 如果两个节点值不同，则返回 false
    • 否则，继续遍历，直到右半部分链表节点遍历结束（因为左半部分长度= 右半部分 or 左半部分长度 - 右半部分长度 = 1）
  • 将右半部分链表重新逆序还原，再重新连接左右部分
  • 返回 true ```cpp /**
    • Definition for singly-linked list.
    • struct ListNode {
    • int val;
    • ListNode *next;
    • ListNode(int x) : val(x), next(NULL) {}
    • }; */

// 将链表start到end之间的节点逆序（包含start，不包含end） ListNode reverseList(ListNode start, ListNode end) { ListNode pre = NULL; ListNode cur = start; while(cur != end) { ListNode next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; }

class Solution { public: bool isPalindrome(ListNode* head) { if(head == NULL || head->next == NULL) return true;

    // 先找到链表中间节点
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast->next != NULL && fast->next->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }   // 此时 slow 指向中间节点

    // 将链表右半部分逆序
    ListNode* rightHead = reverseList(slow->next, NULL);
    slow->next = NULL;    //将左半部分最后指向 NULL

    // 依次比较链表左半部分和逆序后的右半部分，如果存在不同，则不是回文序列
    ListNode* left = head;
    ListNode* right = rightHead;
    while(right != NULL)
    {
        if(left->val != right->val)
            return false;
        left = left->next;
        right = right->next;
    }

    // 最后将链表右半部分重新逆序回原来的顺序，再与左半部分拼接
    rightHead = reverseList(rightHead, NULL);
    slow->next = rightHead;

    return true;
}

};

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 94.69% 的用户 内存消耗：13.4 MB, 在所有 C++ 提交中击败了 56.47% 的用户 ```