题目:
示例 1:
输入:head = [1,2,2,1] 输出:true示例 2:
输入:head = [1,2] 输出:false
提示:
代码如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool isPalindrome(struct ListNode* head) {
if(head==NULL)
{
return true;
}
int copy[100001],num=0;
while(head){
copy[num++]=head->val;
head=head->next;
}
for(int i =0,j=num-1;i<j;i++,j--){
if(copy[i]!=copy[j]){
return false;
}
}
return true;
}
进阶:
上述方法中我开辟了O(n)空间的数组用来存放链表节点的数值,如果要避免使用 O(n)额外空间,那就要改变输入。这里官方给出的题解是把后半段的链表反转,与前半段进行比较。如何找到后半段链表的头呢?这就要用到快慢指针。
struct ListNode* reverseList(struct ListNode* head) {// 反转链表
struct ListNode* prev = NULL;
struct ListNode* curr = head;
while (curr != NULL) {
struct ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
struct ListNode* endOfFirstHalf(struct ListNode* head) {// 快慢指针找到前半链表的尾结点
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast->next != NULL && fast->next->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
bool isPalindrome(struct ListNode* head) {
if (head == NULL) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
struct ListNode* firstHalfEnd = endOfFirstHalf(head);
struct ListNode* secondHalfStart = reverseList(firstHalfEnd->next);
// 判断是否回文
struct ListNode* p1 = head;
struct ListNode* p2 = secondHalfStart;
bool result = true;
while (result && p2 != NULL) {
if (p1->val != p2->val) {
result = false;
}
p1 = p1->next;
p2 = p2->next;
}
// 还原链表并返回结果
firstHalfEnd->next = reverseList(secondHalfStart);
return result;
}
原文地址:https://blog.csdn.net/bbbbb___/article/details/134665938
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_20706.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。