题解 | #链表的回文结构#

链表的回文结构

https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa

解题分为三个步骤,①将链表分为两个部分;②将后一部分反转;③对比前后两个部分,判断是否为回文结构

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//思路:
//①找到链表的中间结点(如果中间结点有两个则找到第二个中间结点)
//②通过中间结点将链表分为两部分,将前半部分的最后一个结点的next设为NULL,并将后半部分进行反转(包含中间结点)
//③将前半部分和反转后的后半部分按顺序对每一对结点进行比较,直到前半部分比较完(即,后半部分也没有结点或后半部分只有一个结点)
//  如果在步骤③中,直到比较结束也没有出现不同的结点,则返回true,否则返回false。
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        ListNode* front = A;
        ListNode* cur = A;
        ListNode* behind = NULL;
        ListNode* next = NULL;
        if(A)
        {
            //将链表从中间结点分为两部分
            ListNode* prev = A -> next;
            while( prev && prev -> next )
            {
                prev = prev -> next -> next;
                cur = cur -> next;
            }
            behind = cur -> next;
            cur -> next = NULL;
            //反转后半部分
            cur = behind;
            if(cur)
            {
                prev = cur -> next;
                while(prev)
                {
                    cur -> next = next;
                    next = cur;
                    cur = prev;
                    prev = prev -> next;
                }
                cur -> next = next;
                //比较前后两部分链表
                ListNode* Front = front;
                ListNode* Behind = cur;
                while(Front && Behind)
                {
                    if(Front -> val != Behind ->val)
                    {
                        return false;
                    }
                    Front = Front -> next;
                    Behind = Behind -> next;
                }
            }
        }
        return true;
    }
};

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-10 11:27
明天又是董事长面,啥时候是个头啊
积极向上的林同学:董事长亲自面试
点赞 评论 收藏
分享
06-25 09:33
厦门大学 Java
程序员饺子:现在日常估计没啥hc了,等到八月多估计就慢慢有了。双九✌🏻不用焦虑的
投递快手等公司7个岗位
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
07-07 11:33
江南大学 Java
已经在暑假实习了 ,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务