首页 > 其他分享 >[牛客]链表的回文结构

[牛客]链表的回文结构

时间:2023-04-22 22:31:48浏览次数:43  
标签:head ListNode struct 回文结构 fast next 链表 牛客 cur

牛客链接


[牛客]链表的回文结构_中间结点

思路:

找中间结点

从中间结点开始对后半段进行逆置

比较前半段和后半段

相等是,不相等不是

[牛客]链表的回文结构_中间结点_02

只需将我们前面写过的链表中间结点,逆置链表的代码复用,并加上如下代码即可

[牛客]链表的回文结构_链表_03

最终代码:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
//返回中间结点
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*slow,*fast;
    slow = fast = head;
    while(fast && fast->next)//考虑到结点个数的奇
    {
        slow = slow->next;
        fast= fast->next->next;
    }
    return slow;


}

//链表逆置
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur,*newHead;
    cur = head;
    newHead = NULL;
    while(cur)
    {
        struct ListNode* next = cur->next;
       cur->next = newHead;
       newHead = cur;
       cur = next;
    } 
    return newHead;
}

    bool chkPalindrome(ListNode* head) {
        struct ListNode* mid = middleNode(head);
        struct ListNode* rhead = reverseList(mid);

        while(head && rhead)
        {
            if(head->val != rhead->val)
            return false;

            head = head->next;
            rhead = rhead->next;
        }

        return true;
    }
};


标签:head,ListNode,struct,回文结构,fast,next,链表,牛客,cur
From: https://blog.51cto.com/u_15992140/6215695

相关文章

  • 算法学习day03链表part01-203、707、206--待办
    //这块需求重新进行学习packageLeetCode.linkedlistpart01;publicclassListNode{//结点的值intval;//下一个结点ListNodenext;//节点的构造函数(无参)publicListNode(){}//节点的构造函数(有一个参数)publicLis......
  • 20-4-21--链表--两个有序链表序列的合并
    已知两个非降序链表序列S1与S2,设计函数构造出S1与S2合并后的新的非降序链表S3。输入格式:输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表示序列的结尾(−1不属于这个序列)。数字用空格间隔。输出格式:在一行中输出合并后新的非降序链表,数字间用空格分开,结尾不......
  • 牛客练习赛110
    A.嘤嘤的签到双指针+算贡献用cnt[]来记录当前维护区间1和4的数量,当当前区间不满足要求则移动左指针直到满足要求,再加上贡献即可。当然也可以记录最后的1和4的位置,这样他们位置中较小的那一个的后一个位置就是能满足要求的区间的最左端的左指针,但是该方法就没上一个那么通用了......
  • 牛客网——实现二叉树先序、中序和后序遍历
    title:牛客网——实现二叉树先序、中序和后序遍历题目描述:分别按照二叉树先序,中序和后序打印所有的节点。示例:输入:{1,2,3}返回值:[[1,2,3],[2,1,3],[2,3,1]]备注:$$n\leqslant10^6$$代码如下:(照着别人的代码敲的,待重新实现一遍)/***structTreeNode{* int......
  • 链表
    title:链表2、环形链表快慢指针,快指针一次走两步,慢指针一次走一步。单链表有环的话,快慢指针会相遇。/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/boolhasCycle(structListNode*head){......
  • 剑指Offer——24.反转链表(c语言)
    title:剑指Offer24.反转链表(c语言)定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。示例:输入:1->2->3->4->5->NULL输出:5->4->3->2->1->NULL限制:$$0\leqslant节点个数\leqslant5000$$代码如下:/***Definitionforsingly-linkedlist.......
  • 牛客网——数组中出现次数超过一半的数字
    title:牛客网——数组中出现次数超过一半的数字题目描述:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。示例:输入[1,2,3,2,2,2......
  • 力扣——21.合并两个有序链表(c语言)
    title:力扣——21.合并两个有序链表(c语言)将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例:输入:1->2->4,1->3->4输出:1->1->2->3->4->41、递归实现:/***Definitionforsingly-linkedlist.*structListNode{......
  • 力扣——83.删除排序链表中的重复元素(c语言)
    title:力扣——83.删除排序链表中的重复元素(c语言)题目描述:给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。示例1:输入:1->1->2输出:1->2示例2:输入:1->1->2->3->3输出:1->2->3代码如下:/***Definitionforsingly-linkedlist.*structListNode{*......
  • 牛客小白月赛71 补题记录
    AB:略C:可以转化为比较对数,然后直接模拟即可(longdouble128位表示范围\(-1.2\times10^{-4932}~1.2\times10^{4932}\))代码如下:#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;//------------------------intmain(void){ ios::sync_with_stdi......