给一个单链表的头节点head,如何判断是否为回文链表,是返回true,否则返回false,c语言实现
时间: 2024-09-14 10:08:33 浏览: 38
给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false
判断一个单链表是否为回文链表,可以通过以下步骤实现:
1. 首先找到链表的中点。这可以通过快慢指针的方法来完成,慢指针每次移动一个节点,快指针每次移动两个节点,当快指针到达链表末尾时,慢指针恰好位于链表的中点。
2. 然后将链表的后半部分进行翻转。可以通过递归或者迭代的方式来翻转链表。
3. 接下来比较链表的前半部分和翻转后的后半部分是否相同。
4. 最后,为了保持链表的结构不变,需要将后半部分再次翻转回来,并连接回前半部分,恢复原始链表。
以下是C语言的实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct ListNode {
int val;
struct ListNode *next;
};
// 翻转链表函数
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* curr = head;
while (curr) {
struct ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
// 检测链表是否为回文
bool isPalindrome(struct ListNode* head) {
if (head == NULL || head->next == NULL) return true;
// 找到链表中点
struct ListNode *slow = head, *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
// 翻转后半部分链表
slow->next = reverseList(slow->next);
slow = slow->next;
// 比较前半部分和翻转后的后半部分
struct ListNode* curr = head;
while (slow) {
if (curr->val != slow->val) return false;
curr = curr->next;
slow = slow->next;
}
return true;
}
// 主函数,用于测试
int main() {
// 示例代码中省略了链表的创建和填充,以及测试代码
return 0;
}
```
这段代码没有包含创建和填充链表的部分,也没有测试代码,仅仅展示了如何实现判断单链表是否为回文的功能。在实际使用中,你需要根据具体情况来创建链表,并在`main`函数中调用`isPalindrome`函数进行测试。
阅读全文