首页 > 其他分享 >leetcode-234回文链表

leetcode-234回文链表

时间:2023-04-20 23:24:56浏览次数:49  
标签:head ListNode val next 链表 234 NULL leetcode

回文链表

方法一:借助数组进行判断

把节点的值复制到一个数组中再利用数组进行判断,但是这样需要占用额外的空间

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int>tmp;
    bool isPalindrome(ListNode* head) {
        while(head!=NULL){
            tmp.push_back(head->val);
            head=head->next;
        }
        int n=tmp.size();
        for(int i=0;i<n/2;i++){
            if(tmp[i]!=tmp[n-1-i])
                return false;
        }
        return true;
    }
};

方法二:双指针

  • 思想:为了使空间复杂度为O(1),将原链表的后半部分反转,然后比较前后两部分每个节点的值是否一样,如果都一样,则这个链表是回文链表,但凡有一个值不一样,就不是回文链表
  • 步骤:先找到链表的中间节点,然后把从中间节点的后半部分链表反转,设置两个指针分别指向头指针和中间节点,同时往后遍历并比较每个节点的值进行判断;比较结束要把后半部分链表再反转回来,不要改变初始链表的结果
  • 注意:①反转链表要进行两次,可写一个用于反转链表的函数,需要反转链表时直接调用;②利用快慢指针找链表的中间节点时注意循环条件;③将后半部分链表再反转回来时,注意接收返回值时用pre->next,不能是pre.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    //反转链表的函数
     ListNode* reverseList(ListNode*p){
        ListNode*pre=NULL;
        ListNode*now=p;
        while(now!=NULL){
            ListNode*next=now->next;
            now->next=pre;
            pre=now;
            now=next;
        }
        return pre; 
     }
    bool isPalindrome(ListNode* head) {
        if(head==NULL || head->next==NULL)
            return true;
        //找到链表的中间节点
        // //方法一:快慢指针法
        ListNode*tmp=head,*fast=head,*pre=NULL;
        while(fast!=NULL && fast->next!=NULL){
            pre=tmp;
            tmp=tmp->next;
            fast=fast->next->next;
         }
         
        //方法二:计算链表长度之后找中间节点
        /*ListNode* p=head;
        int cnt=0;
        while(p!=NULL){
            cnt++;
            p=p->next;
        }
        ListNode*tmp=head,*pre=NULL;
        for(int i=0;i<cnt/2;i++){
            pre=tmp;//最终pre指向的是中间节点的前一个节点,方便最后把链表再反转回来
            tmp=tmp->next;   //最终tmp指向的是中间节点
        }*/
             
        //将链表的后半部分反转
        ListNode*mid=reverseList(tmp);
        //比较反转后的前后两部分是否每个节点都相同,如果相同,则是回文链表,否则不是
        ListNode*first=head;
        ListNode*second=mid;
        while(second!=NULL){
            if(first->val!=second->val)
                return false;
            first=first->next;
            second=second->next;
        }
        //把后半部分链表再反转回来,使链表与初始状态一样
        pre->next=reverseList(mid);
        return true;
    }
};

标签:head,ListNode,val,next,链表,234,NULL,leetcode
From: https://www.cnblogs.com/cxyupup/p/17338732.html

相关文章

  • [牛客]链表分割
    编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前。牛客链接最简单思路因为头插必然改变顺序,所以使用尾插大于的尾插到一个链表小于的尾插到一个链表然后链接起来使用哨兵位的头结点,防止太多问题的产生/*structListNode{intval;struc......
  • 单链表的实现
    链表的概念我们知道顺序表的储存方式是一片连续的空间里面储存数据而链表就不一样了,从这个图我们可以看到在一个链表里面有两个储存空间的部分,一部分是用以储存我们的数据,而另一部分储存的是一个结构体的地址,而这个地址指向的空间里面也有两个部分的储存空间用处和上面的一样,直到最......
  • LeetCode 22 括号生成
    LeetCode|22.括号生成数字n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合。示例1:输入:n=3输出:["((()))","(()())","(())()","()(())","()()()"]示例2:输入:n=1输出:["()"]提示:1<=n<=8方案一:递归  当......
  • LeetCode 周赛 341 场,模拟 / 树上差分 / Tarjan 离线 LCA / DFS
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]提问。大家好,我是小彭。上周末有单双周赛,双周赛我们讲过了,单周赛那天早上有事没参加,后面做了虚拟竞赛,然后整个人就不好了。前3题非常简单,但第4题有点东西啊,差点就放弃了。最后,被折磨了一个下午和一个大夜......
  • LeetCode-Go:一个使用 Go 语言题解 LeetCode 的开源项目
    在中国的IT环境里,大多数场景下,学习算法的目的在于通过笔试算法题。但算法书林林总总,有时候乱花渐欲迷人眼。杜甫有诗云:读书破万卷,下笔如有神。不管选择哪本书,只要深入学习,分层次,逐层进阶,一定可以将算法攻克。笔者强烈推荐一个Github开源项目LeetCode-Go,你不仅可以把他当做......
  • LeetCode Top100: 买卖股票的最佳时机 (python)
    LeetCodeTop100: 买卖股票的最佳时机 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这......
  • 四种语言刷算法之对链表进行插入排序
    力扣147. 对链表进行插入排序1、C/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/structListNode*insertionSortList(structListNode*head){structListNode*newHead=head;struc......
  • LeetCode Top100:回文链表 (python)
    LeetCodeTop100:回文链表给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。示例1:输入:head=[1,2,2,1]输出:true示例2:输入:head=[1,2]输出:false提示:链表中节点数目在范围[1,105] 内0<=Node.val<=9 ......
  • LeetCode Top100: 相交链表(Python)
    LeetCodeTop100:相交链表给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。图示两个链表在节点 c1 开始相交:题目数据 保证 整个链式结构中不存在环。注意,函数返回结果后,链表必须 保持其原......
  • LeetCode Top100: 环形链表(python)
     给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从0开始)。注意:pos 不作为参数进行传递 。仅仅是为......