题目----力扣--回文链表

简介: 题目----力扣--回文链表

题目

给你一个单链表的头节点 head ,请你判断该链表是否为

回文链表

。如果是,返回 true ;否则,返回 false

示例 1:

输入:head = [1,2,2,1]

输出:true


示例 2:

                                                         

输入:head = [1,2]

输出:false


提示:

  • 链表中节点数目在范围[1, 105]
  • 0 <= Node.val <= 9

使用链表实现的话,已知回文链表中的元素个数必定是偶数个

那么就可以先判断:

1.如果是奇数个元素那么就必定不是回文链表;

2.如果是偶数个元素再进行判断

 

因为是单链表

所以只能从头到尾进行遍历

回文链表具有以下特点:

第一个元素和第n个元素相同

第二个元素和第n-1个元素相同

...

那么我们发现实际上在n/2之前的元素与在n/2之后的元素只不过是将顺序翻了过来

这个时候我们就想到栈的特点后进先出

那么也就可以实现将顺序翻过来

这个时候栈内所存的实际上就是与原链表相反的元素顺序

那么可以设置两个指针,一个指向头一个元素 一个指向最后一个元素

一个往后 一个往前

进行对比

元素相同则头指针前进,尾指针不回退;
元素不同则头指针不前进,尾指针回退

进行循环比较,每比较

如果比较到最后尾指针和头指针没有重合的话,那么就说明不是回文链表

反之则是。

 

代码题解

//先创建回文检索函数
struct ListNode* frontPoiner;
bool recursivelyCheck(struct ListNode* currentNode) {
    if (currentNode != NULL) {
        if (!recursivelyCheck(currentNode->next)) {
            return false;
        }
        if (currentNode->val != frontPoiner->val) {
            return false;
        }
        frontPoiner = frontPoiner->next;
    }
    return true;
}
//主要函数
bool isPalindrome(struct ListNode* head) {
    frontPoiner = head;
    return recursivelyCheck(head);
}
目录
相关文章
|
18天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
15 2
|
18天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
11 1
|
18天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
13 1
|
9天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
18天前
|
Java 索引
力扣经典150题第五十六题:环形链表
力扣经典150题第五十六题:环形链表
11 0
|
2月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
1月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
1月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
1月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
14 2
|
2月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
31 1