234 Palindrome Linked List 回文链表
2024-08-30 23:01:57
请检查一个链表是否为回文链表。
进阶：
你能在 O(n) 的时间和 O(1) 的额外空间中做到吗？
详见：https://leetcode.com/problems/palindrome-linked-list/description/
Java实现：
方法一：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
//0个节点或是1个节点
if(head==null||head!=null&&head.next==null){
return true;
}
ListNode slow=head;
ListNode fast=head;
Stack<Integer> stk=new Stack<Integer>();
stk.push(head.val);
while(fast.next!=null&&fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
stk.push(slow.val);
}
//链表长度为偶数
if(fast.next!=null){
slow=slow.next;
}
while(slow!=null){
int tmp=stk.pop();
if(slow.val!=tmp){
return false;
}
slow=slow.next;
}
return true;
}
}
方法二：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
//0个节点或是1个节点
if(head==null||head!=null&&head.next==null){
return true;
}
ListNode slow=head;
ListNode fast=head;
ListNode first=null;
while(fast!=null&&fast.next!=null){
first=slow;
slow=slow.next;
fast=fast.next.next;
}
fast=first.next;
first.next=null;
ListNode pre=null;
ListNode next=null;
while(fast!=null){
next=fast.next;
fast.next=pre;
pre=fast;
fast=next;
}
first=head;
fast=pre;
while(first!=null&&fast!=null){
if(first.val!=fast.val){
return false;
}
first=first.next;
fast=fast.next;
}
return true;
}
}
C++实现：
方法一：
/**
* 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==nullptr||head->next==nullptr)
{
return true;
}
ListNode *slow=head;
ListNode *fast=head;
stack<int> stk;
stk.push(head->val);
while(fast->next&&fast->next->next)
{
slow=slow->next;
fast=fast->next->next;
stk.push(slow->val);
}
if(!fast->next)
{
stk.pop();
}
while(slow->next)
{
slow=slow->next;
int tmp=stk.top();
if(slow->val!=tmp)
{
return false;
}
stk.pop();
}
return true;
}
};
方法二：
/**
* 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||!head->next)
{
return true;
}
ListNode *slow=head;
ListNode *fast=head;
ListNode *first=nullptr;
while(fast&&fast->next)
{
first=slow;
slow=slow->next;
fast=fast->next->next;
}
fast=first->next;
first->next=nullptr;
ListNode *pre=nullptr;
ListNode *next=nullptr;
while(fast)
{
next=fast->next;
fast->next=pre;
pre=fast;
fast=next;
}
first=head,fast=pre;
while(first&&fast)
{
if(first->val!=fast->val)
{
return false;
}
first=first->next;
fast=fast->next;
}
return true;
}
};
参考：https://www.cnblogs.com/grandyang/p/4635425.html
最新文章
- Java基础知识点4：继承
- Request 和 Response 原理
- 你知不知道 Cookie正在泄露你的隐私！
- Topcoder SRM 619 DIv2 500 --又是耻辱的一题
- 开发一个简单实用的android紧急求助软件
- socket编程概述
- 如何使用 SQL Developer 导出数据
- c 语言练习__去掉多余的空白字符_修正
- java中List的排序功能的实现
- [译]脱离jQuery，使用原生Ajax
- DataGridView绘制序号
- 纯手工打造dropdownlist控件
- UESTC-888-Absurdistan Roads(kruskal+floyd)
- SSH整合方案2
- Hibernate（十五）：QBC检索、本地SQL检索和HQL删除
- 04 Django REST Framework 认证、权限和限制
- Ajax 要点
- 20155216 Exp3 免杀原理与实践
- Python读文本文件
- Hbase导入MapReduce数据的时候提示Running Job XXXX后就一直卡着不动