带你粗略了解C++回文链表

回文链表是指从正着和反着读都是一样的链表。C++回文链表则是要求用C++语言实现回文链表的创建和判断。

回文链表的创建

创建回文链表的过程相对简单，首先需要定义一个链表节点的结构体，如下：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

接下来的步骤是创建链表。这里以一个简单的例子进行说明，假设需要创建一个值为1->2->3->2->1的回文链表。代码如下：

ListNode* createPalindromeList() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(2);
    head->next->next->next->next = new ListNode(1);
    return head;
}

可以看到，这里我们直接按照题目要求手动链接每个节点，最终返回链表的头结点即可。

回文链表的判断

判断回文链表是一个比较棘手的问题，首先需要明确的是，判断回文链表的最简单方法是将链表反转，然后与原链表进行比较。但是，这样做会破坏原链表结构，不符合一般需求。

在不破坏原链表的前提下，我们需要先确定链表的中点，然后将链表的后半段反转。接着，逐个比较前半段和反转后的后半段节点值是否相等。

这个过程可以用快慢指针来进行。首先，定义两个指针fast和slow，均指向链表的头结点。然后，fast指针每次往后移动两个节点，slow指针每次往后移动一个节点。当fast到达链表末尾时，slow指针则指向链表的中点。

代码如下：

bool isPalindrome(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return true;
    }
    ListNode *fast = head, *slow = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode *p = slow->next, *q = NULL, *r = NULL;
    slow->next = NULL;
    while (p != NULL) {
        q = p->next;
        p->next = r;
        r = p;
        p = q;
    }
    while (r != NULL) {
        if (head->val != r->val) {
            return false;
        }
        head = head->next;
        r = r->next;
    }
    return true;
}

其中，变量p即为slow指针的后半部分，q为用于遍历的中间变量，r为反转后的后半部分。最后，依次比较前半部分和后半部分的节点值是否相等即可。

示例

下面以两个具体的例子来说明回文链表的创建和判断。

示例一

要求创建一个值为1->2->3->2->1的回文链表。

首先，通过createPalindromeList函数创建该链表。

ListNode* head = createPalindromeList();

当head作为参数传递到isPalindrome函数中时，isPalindrome函数会自动判断head对应的链表是否为回文链表。

bool result = isPalindrome(head);

对于该链表而言，isPalindrome函数返回值为true，即该链表是回文链表。

示例二

要求创建一个值为1->2->3->4->5的链表。

首先，通过如下代码创建该链表。

ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);

当head作为参数传递到isPalindrome函数中时，isPalindrome函数会自动判断head对应的链表是否为回文链表。

bool result = isPalindrome(head);

对于该链表而言，isPalindrome函数返回值为false，即该链表不是回文链表。

阅读剩余 58%