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

题目

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

示例:

  1. 输入: 1->2
  2. 输出: false
  3. 输入: 1->2->2->1
  4. 输出: true
  5. 输入: 1->2->3->2->1
  6. 输出: true

解答 & 代码

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

算法流程:

  • 如果链表为空或只有一个节点,直接返回 true
  • 遍历链表找到中间节点:使用双指针 slowfast,初始时都指向链表第一个节点,
    • 如果 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% 的用户 ```