首页 > 试题广场 >

判断一个链表是否为回文结构

[编程题]判断一个链表是否为回文结构
  • 热度指数：203428 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个链表，请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围： 链表节点数 ，链表中每个节点的值满足
示例1

输入

{1}

输出

true
示例2

输入

{2,1}

输出

false

说明

2->1
示例3

输入

{1,2,2,1}

输出

true

说明

1->2->2->1

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
C
湫湫宁头像 湫湫宁 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */
#include <stdbool.h>
#include <stdlib.h>
struct ListNode* reverval(struct ListNode* head)
{
    if(head == NULL || head->next == NULL)
    {
        return head;
    }
    struct ListNode* rhead = reverval(head->next);
    head->next->next = head;
    head->next = NULL;
    return rhead;
}
struct ListNode* copyList(struct ListNode* head)
{
    if (head == NULL) return NULL;  
    struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    newHead->val = head->val;
    newHead->next = NULL;

    struct ListNode* current = newHead;  
    head = head->next;  

    while (head != NULL) {  
        struct ListNode* new = (struct ListNode*)malloc(sizeof(struct ListNode));
        new->val = head->val;
        new->next = NULL;

        current->next = new;  
        current = current->next;  
        head = head->next;  
    }  
    return newHead;  
}
bool isPail(struct ListNode* head ) {
    // write code here
    struct ListNode* ohead = copyList(head);
    struct ListNode* rhead = reverval(head);

    while(ohead)
    {
        if(ohead->val != rhead->val)
        {
            return false;
        }
        ohead = ohead->next;
        rhead = rhead->next;
    }
    return true;
}
先将head copy一份防止翻转时发生改变，再将链表翻转，最后进行比较
发表于 2024-08-15 15:13:34 回复(0)
C
南宫梦凝头像 南宫梦凝 
int lenth(struct ListNode* p){
    int num = 0;
    while(p != NULL){
        num++;
        p = p->next;
    }
    return num;
}
bool isPail(struct ListNode* head ) {
    // write code here
    struct ListNode*p = head;
    int len = lenth(p);
    int* correct = (int*)calloc(len, sizeof(int));
    int* reverse = (int*)calloc(len, sizeof(int));
    int i = 0;
    while(p != NULL){
        correct[i++] = p->val;
        p = p->next;
    }
    p = head;
    i = len - 1;
    while(p != NULL){
        reverse[i--] = p->val;
        p = p->next; 
    }
    int sameNum = 0;
    for(i = 0; i < len; i++){
        if(correct[i] == reverse[i]){
            sameNum++;
        }
    }
    if(sameNum == len){
        return true;
    }else{
        return false;
    }
}

编辑于 2024-04-08 17:08:49 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
bool isPailArr(int *Arr, int Len) {
    if(Len<2)
        return true;
    if(!isPailArr(Arr+1, Len-2))
        return false;
    if(Arr[0]==Arr[Len-1])
        return true;
    return false;
}
bool isPail(struct ListNode* head ) {
    struct ListNode *p;
    int *buffer,i,res;
    if(head==NULL || head->next==NULL)
        return head;
    i=0;
    p=head;
    while(p!=NULL) {
        i++;
        p = p->next;
    }
    buffer = (int*)malloc(i*sizeof(int));
    i=0;
    p=head;
    while(p!=NULL) {
        buffer[i++] = p->val;
        p = p->next;
    }
    res = isPailArr(buffer, i);
    free(buffer);
    
    return res;
}

编辑于 2024-03-15 22:26:16 回复(0)
C
夜雨潇湘人断肠头像 夜雨潇湘人断肠
struct ListNode* reserve(struct ListNode** phead)
{
    struct ListNode*head=*phead;
    struct ListNode*nest=head->next;
    head->next=NULL;
    while(nest->next)
    {
        struct ListNode*nnest=nest->next;
        nest->next=head;
        head=nest;
        nest=nnest;
    }
    nest->next=head;
    return nest;
}
bool isPail(struct ListNode* head ) {
    struct ListNode* phead=head;
    int len = 0;
    while(phead)
    {
        phead = phead->next;
        len++;
    }
    if(len==1)
    {
        return true;
    }
    len = len/2;
    struct ListNode* pphead=head;
    while(len)
    {
        len--;
        pphead=pphead->next;
    }
   struct ListNode* cur= reserve(&pphead);
    while(cur)
    {
        if((cur->val)!=(head->val))
        {
            return false;
        }
        cur = cur->next;
        head=head->next;
    }
    return true;
}
发表于 2024-03-03 10:39:53 回复(1)
C
孔明KongMing头像 孔明KongMing 
bool isPail(struct ListNode* head) { //struct ListNode*定义链表节点
    struct ListNode* fast = head; //fast快指针（走两步）
    struct ListNode* slow = head; //slow慢指针（走一步）
    struct ListNode* nex = NULL; //nex初始设置为NULL;nex用来存储fast->next
    if (NULL == fast || NULL == fast->next) {
        return true;
    }
    //当fast不为空 and fast的next不为空的时候，fast走两步，slow走一步
    while (NULL != fast && NULL != fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    //当fast为空，走出链表
    fast = slow->next;  //slow为链表的中值。fast赋值为slow的next
    slow->next = NULL;  //断链
    //fast赋值为slow的next,反转链表 1->2->3<-2<-1
    while (NULL != fast) {
        nex = fast->next;   //存储fast的next
        fast->next = slow;  //fast指向slow
        slow = fast;        //slow指针指向fast指针指向的值
        fast = nex;         //fast指针指向nex指针指向的值
    }
    fast = head;            //fast在上一个循环为null才跳出，slow指向最后一个节点；将fast指向头节点，开始比较val;1->2->3<-2<-1
    //当fast与slow不为空时
    while (NULL != fast && NULL != slow) { 
        if (fast->val != slow->val) //如果值不相等返回false
        { return false;}
        fast = fast->next;
        slow = slow->next;
    }
    return true;   //返回true
}
采用快慢指针与反转链表思想
发表于 2023-11-12 11:15:00 回复(0)
C
头发2020头像 头发2020
屎山法 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */
#include <stdbool.h>
#include <stdlib.h>
bool isPail(struct ListNode* head ) {
    // write code here
    struct ListNode* ori = (struct ListNode*)malloc(sizeof(struct ListNode));
    ori->val = 0;
    ori->next = NULL;
    struct ListNode* head2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    head2->val = 0;
    head2->next = NULL;
    struct ListNode* generatep = ori;
    struct ListNode* generatep2 = head2;
    while(head){
        struct ListNode* t = (struct ListNode*)malloc(sizeof(struct ListNode));
        t->val = head->val;
        t->next = NULL;
        struct ListNode* t2 = (struct ListNode*)malloc(sizeof(struct ListNode));
        t2->val = head->val;
        t2->next = NULL;
        generatep->next = t;
        generatep = t;
        generatep2->next = t2;
        generatep2 = t2;
        head = head->next;
    }
    struct ListNode* rev = NULL;
    struct ListNode* t = NULL;
    head2 = head2->next;
    while (head2) {
        t = head2->next;
        head2->next = rev;
        rev = head2;
        head2 = t;
    }
    ori = ori->next;
    while (ori){
        if (ori->val!=rev->val) return false;
        ori=ori->next;
        rev=rev->next;
    }
    return true;
}


发表于 2023-08-03 11:57:25 回复(0)
C
三个和尚头像 三个和尚 
#include <stdbool.h>
bool isPail(struct ListNode* head ) {
    // write code here
    if (head->next == NULL) {
        return true;
    }
    //找到中点slow，如果是偶数链，slow在中点偏右
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    //翻转后面一段链表
    struct ListNode* cur = slow;
    struct ListNode* pre = NULL;
    struct ListNode* nex = NULL;
    while (cur) {
        nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    //左右同时往中间走，如果能走完，有两种情况，单数链的结果是ab都是null，偶数链的结果是a有值b是null
    struct ListNode* a = head;
    struct ListNode* b = pre;
    while (a->val == b->val && a!=NULL && b!=NULL){
        a = a->next;
        b = b->next;
    }
    if (b==NULL) {
        return true;
    }else {
        return false;
    }
}

发表于 2023-05-26 09:11:56 回复(0)
C
爱唱歌的黑眼圈头像 爱唱歌的黑眼圈 
bool isPail(struct ListNode* head ) {
    // write code here
    int size=0;
    struct ListNode* p=head;
    while(p){
        size++;
        p=p->next;
    }
    int *arr=malloc(sizeof(int)*size);
    p=head;
    int i=0,j=size-1;
    while(p){
        arr[i]=p->val;
        p=p->next;
        i++;
    }
    i=0;
    while(i<j){
        if(arr[i]==arr[j]){
            i++;
            j--;
        }
        else{
            return false;
        }
    }
    return true;
}

发表于 2023-02-22 22:10:38 回复(0)
C
lijd头像 lijd 
#include <stdbool.h>
bool isPail(struct ListNode* head ) {
    // write code here
    if (head == NULL || head->next == NULL) {
        return  true;
    }

    int list[100000] = {0}, iNum = 0, i = 0;

    while (head) {
        list[iNum++] = head->val;
        head = head->next;
    }

    for (i = 0; i < iNum/2; i++) {
        if (list[i] != list[iNum - i - 1]) {
            return  false;
        }
    }

    return  true;
}

发表于 2023-01-17 10:49:46 回复(0)
C
80后大叔头像 80后大叔

转换成数组要简单一些。快慢指针找中间点，然后反转右侧的链表，再左右对比比较考验代码能力

bool isPail(struct ListNode* head ) {
    // write code here
    if(head==NULL) return true;
    int list[100000]={0};
    int num=0;
    struct ListNode* p = head;
    while(p!=NULL) {
        list[num++] = p->val;
        p=p->next;
    }
    for(int i=0; i<num/2; i++) {
        if(list[i] != list[num-1-i]) return false;
    }
    return true;
}
发表于 2022-11-15 17:44:06 回复(0)
C
牛客171489173号头像 牛客171489173号 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */
#include <stdbool.h>
typedef struct ListNode Node;
bool isPail(struct ListNode* head ) {
    // write code here
    if(head == NULL || head ->next == NULL){
        return true;
    }
    Node *p1 = head;
    Node *p2 = head;
    //首先找到中点，当p2->next->next为 NULL，那么此时p1刚好在中点
    while(p2 != NULL && p2->next != NULL){
        p2 = p2->next->next;
        p1 = p1->next;
    }
    //快指针到尾判断,如果p2不为空，说明链表的长度是奇数个
    if(p2 != NULL) {
        p1 = p1->next;
    }
    Node *p = p1;
    Node *pre = NULL;
    while(p != NULL){
        Node *q = p->next;
        p->next = pre;
        pre = p;
        p = q;
    }
    while(pre != NULL){
        if(pre->val != head->val){
            return false;
        }    
        pre = pre->next;
        head = head->next;
    }
    
    return true;
}

发表于 2022-05-06 00:54:15 回复(0)
C
阿金要努力头像 阿金要努力 
struct ListNode* MidListNode(struct ListNode* head )
{
    struct ListNode* fast=head,*slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}
struct ListNode* ReverseListNode(struct ListNode* head)
{
    struct ListNode* tail=head,*prev=NULL;
    while(tail)
    {
        struct ListNode* next=tail->next;
        tail->next=prev;
        prev=tail;
        tail=next;
    }
    return prev;
}
bool isPail(struct ListNode* head ) 
{
    struct ListNode* mid=MidListNode(head);
    struct ListNode* reverse=ReverseListNode(mid);
    while(head&&reverse)
    {
        if(head->val==reverse->val)
        {
            head=head->next;
            reverse=reverse->next;
        }
        else
            return false;
    }
    return true;
}

发表于 2022-05-04 00:54:31 回复(0)
C
已注销头像 已注销 
struct ListNode *reverselist(struct ListNode *list, int m, int n);

bool isPail(struct ListNode* head ) {
    // write code here
    int count = 0;
    struct ListNode *reverlist;
    
    if (head == NULL || head->next == NULL) {
        return true;
    }
    for (struct ListNode *p = head; p != NULL; p = p->next) {
        count++;
    }
    reverlist = reverselist(head, (count % 2 == 0 ? count / 2 + 1 : count / 2 + 2), count);
    for (struct ListNode *p = head, *q = reverlist; q != NULL; p = p->next, q = q->next) {
        if (p->val != q->val) {
            return false;
        }
    }
    
    return true;
}

struct ListNode *reverselist(struct ListNode *head, int m, int n) {
    struct ListNode *prev, *cur, *next, *prev_begin;
    int count = 1;
    
    if (head == NULL || head->next == NULL || m == n) {
        return head;
    }
    prev_begin = NULL;
    prev = head;
    for ( ; count < m; count++) {
        prev_begin = prev;
        prev = prev->next;
    }
    cur = prev->next;
    next = cur->next;
    prev->next = NULL;
    while (cur != NULL && count < n) {
        cur->next = prev;
        prev = cur;
        cur = next;
        next = (next != NULL ? next->next : NULL);
        count++;
    }
    head = prev;
    
    return head;
}

发表于 2022-03-23 12:45:20 回复(0)
C
莫小雨so头像 莫小雨so 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */
#include<stdlib.h>
bool isPail(struct ListNode* head ) {
    int *arr = (int *)malloc(sizeof(int) * 10000000);
    struct ListNode *p = head;
    int i = 0, len = 0, j = 0;
    while(p)
    {
        *(arr +(len ++)) = p->val;
        p = p->next;
    }
    i = 0;
    j = len - 1;
    while(i < j)
    {
        if(*(arr +(i ++)) != *(arr +(j --))) return false;
    }
    free(arr);
    return true;
}

发表于 2022-03-04 12:25:56 回复(0)
C
CreatorSY头像 CreatorSY 
#include <stdbool.h>
bool isPail(struct ListNode* head ) {
    struct ListNode *tmp = head;
    int len = 0;

    while(tmp != NULL) {
        len++;
        tmp = tmp->next;
    }
    int *nums = calloc(sizeof(int), len);
    for (int i = 0; i < len; i++, head = head->next)
        nums[i] = head->val;
    for (int i = 0; i < len; i++)
        if (nums[i] != nums[len - i - 1])
            return false;

    return true;
}
发表于 2022-01-06 23:10:47 回复(0)
C
小酷爱头像 小酷爱 
bool isPail(struct ListNode* head ) {
    //我用数组保存链表每块空间的值，这方法可以不改变链表
    struct ListNode* cur = head;
    int arr[10000000] = {0};
    int size = 0;//记录链表的大小
    while(cur)
    {
        arr[size++] = cur->val;
        cur = cur->next;
    }
    
    int i = 0, j = size-1;
    while(i < j)
    {
        if(arr[i++] != arr[j--])
            return 0;
    }
    return 1;
}

发表于 2021-11-07 21:13:25 回复(0)
C
luo_2021头像 luo_2021 
int isPail(struct ListNode* head ) {
    // write code here
    if(head == NULL)
    {
        return 0;
    }
    else if(head->next != NULL)
    {
        //快慢指针
        struct ListNode *p1 = head; //慢
        struct ListNode *p2 = head; //快
        while(p2->next != NULL && p2->next->next != NULL)
        {
            p2 = p2->next->next;
            p1 = p1->next;
        }
        
        //快指针到尾判断
        if(p2->next != NULL)
        {
            p2 = p2->next;
        }
        
        //分割
        struct ListNode *p3 = p1->next;
        p1->next = NULL;
        
        //反转后半段链表
        struct ListNode *p4 = NULL;
        struct ListNode *p5 = p3;
        while(p3 != NULL)
        {
            p5 = p3->next;
            p3->next = p4;
            p4 = p3;
            p3 = p5;
        }
        
        while(p2 != NULL)
        {
            if(head->val != p2->val)
            {
                return 0;
            }
            head = head->next;
            p2 = p2->next;
        }
        
        return 1;
    }
    else
    {
        return 1;
    }
}

用快慢指针与反转链表判断回文链表


发表于 2021-10-16 11:48:16 回复(1)
C
牛客830308422号头像 牛客830308422号 
#define MAX_LEN 1000000
bool isPail(struct ListNode* head ) {
    // write code here
    int val[MAX_LEN] = {0};
    struct ListNode *p =head;
    int idx = 0;
    while (p) {
        val[idx++] = p->val;
        p = p->next;
    }
    for (int i = 0, j = idx - 1; i < j; i++, j--) {
        if (val[i] != val[j]) {
            return false;
        }
    }
    return true;
}

发表于 2021-09-14 00:06:14 回复(0)
提交观点

问题信息

链表 双指针
难度：
20条回答 8854浏览

热门推荐

通过挑战的用户

查看代码

相关试题

判断一个链表是否为回文结构

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号