234. Palindrome Linked List【easy】
2024-09-04 00:12:49
234. Palindrome Linked List【easy】
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
解法一：
/**
* 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 != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;
} slow->next = reverseList(slow->next);
slow = slow->next; while (slow != NULL) {
if (head->val != slow->val) {
return false;
}
slow = slow->next;
head = head->next;
} return true;
} ListNode * reverseList(ListNode* head)
{
if (head == NULL) {
return NULL;
} ListNode * pre = NULL;
while (head != NULL) {
ListNode * next = head->next;
head->next = pre;
pre = head;
head = next;
} return pre;
} };
关键点：
1、快慢指针找到中间位置
2、链表翻转
解法二：
class Solution {
public:
ListNode* temp;
bool isPalindrome(ListNode* head) {
temp = head;
return check(head);
}
bool check(ListNode* p) {
if (NULL == p) return true;
bool isPal = check(p->next) && (temp->val == p->val);
temp = temp->next;
return isPal;
}
};
递归，参考了@alex.tsitsura 的代码，就是利用了每一步递归的时候都有自己的栈空间的性质搞的。
一开始就是check(p->next)走到黑，然后就是到了最后一个节点了，我们比较一下最后一个节点和第一个节点的值；然后就执行下面的temp = temp->next，这个时候刚才那层递归也已经退栈了，现在我们的p对应的就是倒数第二个节点，temp对应的就是第二个节点；这样以此类推的搞下去，最后得解。
解法三：
上面的递归解法可能有些难以理解，可以改为如下：
class Solution {
public:
bool isPalindrome(ListNode* head) {
return check(head, head);
}
bool check(ListNode*& head, ListNode* p) {
if(!p) { return true; }
bool isPal = check(head, p->next);
if(head->val != p->val) {
return false;
}
head = head->next;
return isPal;
}
};
参考了@Meng-Ju 的代码
最新文章
- sublime 配置jade高亮显示
- Themida和Winlicense加壳软件脱壳教程
- React Native实例
- duilib\utils\utils.h(251) : error C2504: “VARIANT”: 未定义基类
- ASP.NET中EVAL用法大全
- jetty-run运行报错的原因
- Oracle RAC OCR 的备份与恢复
- c++字符串的输入的思考
- 推荐 | Vue 入门&进阶路线
- C++编程剖析 问题 方案 和设计准则
- PHP工厂方法模式
- java 多线程中的锁的类别及使用
- SQL 必知必会·笔记<1>了解SQL
- 编译安装openssl
- 【319】Python 通过 Twilio 发短信
- 亚马逊中国耳机巨头Jabra官方旗舰店上线
- 我的Git之旅(1)---git安装、github注册以及一些基本命令
- java学习笔记2015-6-5
- 为什么写《Tomcat内核设计剖析》
- nginx下pagespeed使用详解