每日一题---OJ题: 链表的回文结构

片头

嗨! 小伙伴们,大家好! 今天我们来一起学习这道OJ题--- 链表的回文结构

嗯...这道题好像不是很难,我们来分析分析

举个例子:

我们可以看到,上图中的两个链表都是回文结构: 即链表的回文结构是指一个链表中的结点值从前往后读和从后往前读都是一样的结构。也就是说，链表的顺序是回文的。

例如，以下链表是回文结构： 1 -> 2 -> 3 -> 2 -> 1

而以下链表不是回文结构： 1 -> 2 -> 3 -> 4 -> 5

那我们怎么判断是不是链表的回文结构呢?

思路1 : 我们可以先找到链表的中间结点,然后反转从这个中间结点开始一直到最后一个结点,并且将反转后的新结点返回,最后定义两个变量,分别去遍历链表的头结点和新结点

比如:

我们定义2个变量,A表示指向链表的头结点(第一个结点),rmid 表示指向反转链表返回的新结点

我们让 A 和 rmid 指向的结点依次比较,如果中途 A 指向结点的值不等于rmid结点指向的值,那么直接退出循环,返回 false;如果比较到 A 和 rmid 都为空, 那么返回 true

第一次比较: A 和 rmid 指向的结点的数据域都相等, 那么指针 A 向后走一步, 指针 rmid 向后走一步

第二次比较: A 和 rmid 指向的结点的数据域都相等, 那么指针 A 向后走一步, 指针 rmid 向后走一步

第三次比较: rmid指针指向NULL, 退出循环, 返回 true

我们查找链表的中间结点的代码如下:

    //找出中间结点
    struct ListNode* Find(struct ListNode* head){
        struct ListNode* fast = head;            //fast指针指向第一个结点
        struct ListNode* slow = head;            //slow指针指向第一个结点
        while(fast && fast->next){            // 当 fast 并且 fast->next 不为空时,进入循环                   
            slow = slow->next;                //slow指针每次走一步
            fast = fast->next->next;          //fast指针每次走两步
        }
        return slow;                          //返回slow指针指向的结点,就是中间结点
    }

具体的关于链表的中间结点讲解在这里哦, 小伙伴们可以点击查看: 链表的中间结点 (注意: 点击蓝色字体就可以跳转到相应的文章哦!)

我们找到链表的中间结点后,我们就可以反转从这个中间结点开始一直到最后一个结点

反转链表的代码如下:

    //反转链表
    struct ListNode* Reverse(struct ListNode* head){
        struct ListNode* n1 = nullptr;            //定义一个n1指针指向NULL
        struct ListNode* n2 = head;               //定义一个n2指针指向头结点
        struct ListNode* n3 = head->next;         //定义一个n3指针指向头结点的下一个结点

        while(n2 != nullptr){                     //判断n2是否为空
            n2->next = n1;                        //如果n2非空,就把n2的next指针指向n1
            n1 = n2;                              //把n2赋给n1
            n2 = n3;                              //把n3赋给n2
            if(n3){                               //如果n3非空,就让n3指向n3的下一个结点
                n3 = n3->next;
            }
        }
        return n1;                                //最后n2和n3都为空,n1恰好是新链表的头结点
    }

具体的关于反转链表的讲解可以戳这里哦,小伙伴们可以点击查看: 反转链表 (注意: 点击蓝色字体就可以跳转到相应的文章哦!)

好啦,准备工作做好了以后,我们就可以在题目所给的方法里面写代码啦!

首先,我们要定义一个结点指针,用来接收返回过来的中间结点; 其次,我们需要定义另外一个结点指针,用来接收反转链表后的新结点。

将两个指针所指向的结点进行比较，如果它们的数据域不同，说明链表不是回文结构, 则跳出循环, 返回 false ；如果数据域相同，那么两个指针同时往后走一步，继续比较下一个结点，直到其中一个指针指向NULL, 说明链表是回文结构, 返回 true。

整体代码如下：

class PalindromeList {
  public:
    //找出中间结点
    struct ListNode* Find(struct ListNode* head) {
        struct ListNode* fast = head;            //fast指针指向第一个结点
        struct ListNode* slow = head;            //slow指针指向第一个结点

         // 当 fast 并且 fast->next 不为空时,进入循环
        while (fast && fast->next) {         
            slow = slow->next;         //slow指针每次走一步
            fast = fast->next->next;   //fast指针每次走两步
        }
        return slow;                   //返回slow指针指向的结点,就是中间结点
    }

 //反转链表
    struct ListNode* Reverse(struct ListNode* head){
        //定义一个n1指针指向NULL
        struct ListNode* n1 = nullptr;           
         //定义一个n2指针指向头结点
        struct ListNode* n2 = head;              
        //定义一个n3指针指向头结点的下一个结点
        struct ListNode* n3 = head->next;

        while(n2 != nullptr){       //判断n2是否为空
            n2->next = n1;          //如果n2非空,就把n2的next指针指向n1
            n1 = n2;                //把n2赋给n1
            n2 = n3;                //把n3赋给n2
            if(n3){                 //如果n3非空,就让n3指向n3的下一个结点
                n3 = n3->next;
            }
        }
        return n1;                 //最后n2和n3都为空,n1恰好是新链表的头结点
    }

    bool chkPalindrome(ListNode* A) {
         //定义mid指针,用来接收中间结点
        struct ListNode* mid = Find(A);    
       //定义r指针,用来接收将链表反转后的新结点 
        struct ListNode* r = Reverse(mid); 
        ListNode* pcur = A;

        //当两个指针都不为空时,进入while循环
        while (pcur && r) {
    //如果两个指针指向的结点的数据域不相同,说明链表不是回文结构,那么返回 false
            if (pcur->val != r->val) {
                return false;
            }
    //如果两个指针指向的结点数据域相同,那么继续比较下一个结点
            pcur = pcur->next;
            r = r->next;
        }
        //其中一个指针走向NULL,说明是链表回文结构,返回 true
        return true;
    }
};