使用双指针方法来判断链表是否是一个会问链表

简介: 使用双指针方法来判断链表是否是一个会问链表

回文链表


给定一个链表的 头节点head 请判断其是否为回文链表。

如果一个链表是回文,那么链表节点序列从前往后看和从后往前看是相同的。

示例 1:


image.png


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

输出: true

示例 2:

image.png


输入: head = [1,2]

输出: false


解题思路


我们做过数组列表是否回文的题目,如果是数组时我们可以使用双指针法来比较两端的元素,并向中间移动。一个指针从起点向中间移动,另一个指针从终点向中间移动。

对于链表我们可以将链表的值复制到数组列表中,再使用双指针法来检查是否为回文。我们在起点放置一个指针,在结尾放置一个指针,每一次迭代判断两个指针指向的元素是否相同,若不同,返回 false;相同则将两个指针向内移动,并继续判断,直到两个指针相遇。

具体步骤如下:

  • 第一步:初始化一个数组变量,用于存储链表的值
  • 第二步: 遍历每一个链表节点,如果不是null就把当前节点的值存到数组里
  • 第三步:使用for循环遍历数组,初始化两个索引,一个指向开始,一个指向结束,两个指针向数组中间聚拢
  • 第四步: 循环内判断两个指针指向的值是否相同,如不不相同说明就不是回文,则返回false
var isPalindrome = function(head) {
    const vals = [];
    while (head !== null) {
        vals.push(head.val);
        head = head.next;
    }
    for (let i = 0, j = vals.length - 1; i < j; i++, j--) {
        if (vals[i] !== vals[j]) {
            return false;
        }
    }
    return true;
};


目录
相关文章
|
6月前
|
存储 Java C++
C++ 引用和指针:内存地址、创建方法及应用解析
C++中的引用是现有变量的别名,创建时需用`&`运算符,如`string &meal = food;`。指针存储变量的内存地址,使用`*`创建,如`string* ptr = &food;`。引用必须初始化且不可为空,而指针可初始化为空。引用在函数参数传递和提高效率时有用,指针适用于动态内存分配和复杂数据结构操作。选择使用取决于具体需求。
93 9
|
6月前
|
存储 C语言
用指针处理链表
用指针处理链表
59 3
|
1月前
|
存储
一篇文章了解区分指针数组,数组指针,函数指针,链表。
一篇文章了解区分指针数组,数组指针,函数指针,链表。
18 0
|
4月前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
51 1
【数据结构OJ题】复制带随机指针的链表
|
3月前
|
Python
【Leetcode刷题Python】138. 复制带随机指针的链表
LeetCode上题目“138. 复制带随机指针的链表”的Python解决方案,包括两种方法:一种是在每个节点后复制一个新节点然后再分离出来形成新链表;另一种是构建一个字典来跟踪原始节点与其副本之间的映射关系,从而处理新链表的构建。
20 1
|
3月前
|
存储 算法 数据处理
指针与链表
指针与链表
65 0
java.lang.NullPointerExceptionMybatisPlus出现,测试,java.lang.NullPointe,空指针异常,public方法少写了一个字段,没加注解
java.lang.NullPointerExceptionMybatisPlus出现,测试,java.lang.NullPointe,空指针异常,public方法少写了一个字段,没加注解
|
5月前
|
存储 算法 数据可视化
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
|
5月前
|
C++ 存储 Java
C++ 引用和指针:内存地址、创建方法及应用解析
'markdown'C++ 中的引用是现有变量的别名,用 `&` 创建。例如:`string &meal = food;`。指针通过 `&` 获取变量内存地址,用 `*` 创建。指针变量存储地址,如 `string *ptr = &food;`。引用不可为空且不可变,指针可为空且可变,适用于动态内存和复杂数据结构。两者在函数参数传递和效率提升方面各有优势。 ```
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表