Python怎么判断一个单链表是否是回文链表
这篇文章主要讲解了“Python怎么判断一个单链表是否是回文链表”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Python怎么判断一个单链表是否是回文链表”吧！
成都创新互联公司专业为企业提供芦淞网站建设、芦淞做网站、芦淞网站设计、芦淞网站制作等企业网站建设、网页设计与制作、芦淞企业网站模板建站服务，十载芦淞做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。
判断一个单链表是否是回文链表。
如：[1, 2, 3, 2, 1] 就是一个回文链表，正着依次看链表中元素和反着依次看链表中元素都是一样的。
解题思路：
必须做的第一个步骤就是判断输入链表是否为空，或者只有一个元素。如果为空或者只有一个元素，则此链表为回文链表返回true。
使用快慢指针，找到链表中点。慢指针一次走一步，快指针一次走两步。
根据找到的链表中点，反转后半部分的链表的所有值，并与整体单链表的值从头依次比对，有一个值不同，则不是回文链表，否则为回文链表。
如输入单链表：[1, 2, 3, 2, 1]
反转后半部分得到的单链表：[1, 2]
Language:C
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/struct ListNode* reverseList(struct ListNode* head) {struct ListNode* pre = (struct ListNode *)malloc(sizeof(struct ListNode));struct ListNode* next = (struct ListNode *)malloc(sizeof(struct ListNode));
pre=NULL;
next=NULL;while(head!=NULL){
next=head->next;
head->next=pre;
pre=head;
head=next;
}return pre;
}bool isPalindrome(struct ListNode* head) {struct ListNode* slow = (struct ListNode *)malloc(sizeof(struct ListNode));struct ListNode* fast = (struct ListNode *)malloc(sizeof(struct ListNode));if(head == NULL || head->next == NULL){return true;
}
fast = head;
slow = head;while(fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
slow = reverseList(slow->next);while(slow){if(head->val != slow->val){return false;
}
head = head->next;
slow = slow->next;
}return true;
}Language:cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/class Solution {public:
bool isPalindrome(ListNode* head) {if(head == NULL || head->next == NULL){
return true;
}
ListNode* slow = head;
ListNode* fast = head;while(fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
slow = reverseList(slow->next);while(slow){if(head->val != slow->val){
return false;
}
head = head->next;
slow = slow->next;
}
return true;
}
ListNode* reverseList(ListNode* head){
ListNode* pre = NULL;
ListNode* next = NULL;while(head!=NULL){next=head->next;
head->next=pre;
pre=head;
head=next;
}
return pre;
}
};感谢各位的阅读，以上就是“Python怎么判断一个单链表是否是回文链表”的内容了，经过本文的学习后，相信大家对Python怎么判断一个单链表是否是回文链表这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是创新互联，小编将为大家推送更多相关知识点的文章，欢迎关注！
当前名称：Python怎么判断一个单链表是否是回文链表
分享URL：http://mswzjz.cn/article/iepieo.html