c语言--力扣简单题目（回文链表）讲解

题目如下：
给你一个单链表的头节点 head ，请你判断该链表是否为

回文链表。

如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1] 输出：true

示例 2：

输入：head = [1,2] 输出：false

提示：

链表中节点数目在范围[1, 105] 内

0 <= Node.val <= 9

结构体定义：

typedef struct Node {
char val;
struct Node* next;
}Node;
typedef Node* List;

第一部分

List head, tail;
Node* p;
p = (Node*)malloc(sizeof(struct Node));
int ch, val,n=0,i=1;
head = p;
tail = p;
head->next = NULL;
printf("请输入链表的内容");
while ((ch = getchar()) != '\n') {
    if (ch == ' ') {
        continue;
    }
    p = (Node*)malloc(sizeof(struct Node));
    p->val = ch-48;
    tail->next = p;
    tail = p;
    tail->next = NULL;
    n += 1;
}

这部分就是一个普通的输入。

第二部分

tail = head->next;//让tail指针指向第一个节点
int* sum = (int*)malloc(n * sizeof(int));
if (n % 2 == 0) {
    for (int n1 = 0; n1 < n; n1++) {
        if (sum[i - 1] != tail->val) {
            sum[i] = tail->val;
            i += 1;
        }
        else {
            sum[i - 1] = 0;
            i -= 1;
        }
        tail = tail->next;
    }
}
else {
    for (int n1 = 0; n1 < n; n1++) {
        if (sum[i - 2] != tail->val) {
            sum[i] = tail->val;
            i += 1;
        }
        else {
            sum[i - 2] = 0;
            i -= 1;
        }
        tail = tail->next;
    }
}
if (sum[1] == 0) {
    printf("true");
}
else
    printf("false");
return 0;

这里我们先让tail指针指向第一个元素所在的节点，之后进行动态内存分配。

我们这里使用了一个毕竟笨的办法，如果有奇数个数字，我们会让用i-2去判断，而不是i-1，比如我们输入121，那么中间的2我们就不进行判断，直接用两个1去判断，如果有偶数个数字，那么我们就用i-1去进行判断。

（我可能解释的不够清楚，请各位大佬帮忙补充）。

原文地址：https://blog.csdn.net/2401_85637543/article/details/142315704

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！