剑指 Offer II 027. 回文链表

日常刷题中

GitHub链接

diwei00 (github.com)https://github.com/diwei00刷题代码都在Exercise库中提交

LeetCode链接

剑指 Offer II 027. 回文链表 - 力扣（LeetCode）https://leetcode.cn/problems/aMhZSa/

题目

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例1

输入: head = [1,2,3,3,2,1]
输出: true

示例2

输入: head = [1,2]
输出: false

题目解析🤨

     首先，回文链表的判断要用第一个节点数据和最后一个节点数据进行比对，然后在用第二个节点和倒数第二个节点数据比对，以此类推。因为这是单链表，他不像顺序表那样可以随机访问数据，只能从前往后遍历链表。

     分析题目发现，数据的比对是链表的前半部分和后半部分进行比较，所以我们需找到链表的中间节点。由于进行比对是前半部分节点数据和后半部分节点数据，所以考虑反转后半部分链表。

     这里找链表的中间节点，用的是快慢指针法，快指针一次走两步，慢指针一次走一步。区分奇偶个数节点链表，当快指针遍历完链表时，慢指针刚好在链表的中间节点。

     这里反转链表，用的是三指针法，为的是反转完可以找到下一个节点。

这里的两个思路在这篇博客中有详细介绍。

反转链表（AND）链表的中间结点_小小太空人w的博客-CSDN博客https://blog.csdn.net/weixin_62353436/article/details/124332827?spm=1001.2014.3001.5501

代码实现（有详细注释）

bool isPalindrome(struct ListNode* head)
{
    struct ListNode* phead = head;
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    //快慢指针找中间节点
    while (fast != NULL && fast->next != NULL)
    {
      
        fast = fast->next->next;
        slow = slow->next;
    }
    struct ListNode* p1 = NULL;
    struct ListNode* p2 = slow;
    struct ListNode* p3 = slow->next;
    //反转后半部分链表
    while (p2 != NULL)
    {
        p2->next = p1;
        p1 = p2;
        p2 = p3;
        if (p3 != NULL)
        {
            p3 = p3->next;
        }
    }
    //比对数据
    while (p1 != NULL)
    {
        if (p1->val == phead->val)
        {
            p1 = p1->next;
            phead = phead->next;
            
        }
        else
        {
            return false;
        }
    }
    //全部数据都相等
    return true;
}

小结

    对于链表的操作，要考虑访问数据是不同于顺序表的，所以思路会有一定的差异。我们需大量的去刷题，锻炼编程思维， 相信坚持下去会有不一样的收获🤨。