首页 > 其他分享 >LeetCode Hot100刷题记录-234.回文链表

LeetCode Hot100刷题记录-234.回文链表

时间:2024-09-10 21:16:00浏览次数:8  
标签:head val arr next 链表 Hot100 234 回文

题目:给你一个单链表的头节点 head ,请你判断该链表是否为
回文链表
。如果是,返回 true ;否则,返回 false 。
PS: 回文 序列是向前和向后读都相同的序列。

解题思路:
遍历链表,将每个元素存放入一个新的数组中。遍历完成后,再用两个指针前后遍历数组来判断两个数字是否相等。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    const arr = new Array();
    while(head) {
        arr.push(head.val);
        head = head.next;
    }
    let i = 0;
    let j = arr.length - 1;
    while(i < j){
        if(arr[i] === arr[j]){
            i++;
            j--;
        } else {
            return false;
        }

    }
    return true;
}

这样的时间复杂度和空间复杂度都为O(n)

** 可以尝试着把空间复杂度降到O(1):
不借助额外的数组,用双指针和原地修改链表的方法。我们将链表分成前后两个部分,反转后半部分的链表,然后通过双指针判断是否是回文。
思路:
使用快慢指针找到链表的中间节点。
反转后半部分的链表。
比较前半部分和后半部分的节点值。
恢复链表(可选,面试时有时候要求恢复原链表)。

标签:head,val,arr,next,链表,Hot100,234,回文
From: https://www.cnblogs.com/gardenOfCicy/p/18407195

相关文章

  • c语言--力扣简单题目(删除排序链表中的重复元素)讲解
    题目如下:给定一个已排序的链表的头head,删除所有重复的元素,使每个元素只出现一次。返回已排序的链表。示例1:输入:head=[1,1,2]输出:[1,2]示例2:输入:head=[1,1,2,3,3]输出:[1,2,3]提示:链表中节点数目在范围[0,300]内-100<=Node.val<=100题目数据保......
  • 重头开始嵌入式第三十七天(数据结构 链表)
    单向链表单向链表是一种常见的数据结构。一、结构组成-节点:单向链表由多个节点组成。每个节点包含两个部分,一个是存储数据的部分,可以存储各种类型的数据,如整数、字符、结构体等;另一个是指向下一个节点的指针,用于连接链表中的各个节点。-头指针:链表有一个特殊的指针称为头......
  • 数据结构—链表
    一:链表1、数组是连续的内存空间;而链表可以不一定是连续的内存空间2、单端链表;从前一个元素指向后一个元素3、链表的功能(1)访问o(n):数组是通过下表或者索引访问元素;链表是通过next指针以此递归的进行查询判断(2)搜索o(n):从头部遍历;知道找到位置(3)插入o(1):(4)删除o(1):4、特......
  • 每日算法随笔:反转链表 II
    明白了!下面我将基于你给的两种方法来详细解释题解,并展示每一步的变化过程。题解:反转链表II这道题要求我们反转链表中从第left个节点到第right个节点的部分,返回反转后的链表。我们会使用两种方法:递归和迭代。示例解析示例1:输入:head=[1,2,3,4,5],left=2,ri......
  • 每日算法随笔:反转链表
    题解:反转链表这道题目要求我们将一个单链表进行反转,返回反转后的链表。链表的反转可以通过迭代和递归两种方法来实现。下面我们将详细解释这两种方法,并通过例子演示每一步的变化过程。方法一:迭代法思路:我们用三个指针来完成链表的反转:prev表示前一个节点,curr表示当前节......
  • Java-实现双向环形链表
            双向链表是一种常用的数据结构,其特点是每个节点不仅包含数据,还持有指向前一个节点和后一个节点的指针。与普通双向链表不同的是,它的哨兵节点的prev指向最后一个元素,而最后一个元素的next指向哨兵。        具体双向普通链表可以参考我的上篇文章,这里......
  • [Python手撕]排序链表
    #Definitionforsingly-linkedlist.#classListNode:#def__init__(self,val=0,next=None):#self.val=val#self.next=nextclassSolution:defsortList(self,head:Optional[ListNode])->Optional[ListNode]:def......
  • 数据结构—单链表的基本操作
    目录1.单链表的初始化2.求表长操作3.按序号查找结点4.按值查找表结点5.插入结点操作6.删除结点操作7.头插法建立单链表8.尾插法建立单链表1.单链表的初始化 带头结点: boolInitList(LinkList&L){       //带头结点的单链表的初始化  L=(......
  • C ++ 从单链表到创建二叉树到二叉树的遍历(结构体)
    首先我们要了解二叉树的数据结构是什么,本质上二叉树是一个有两个节点的链表,我们先了解的单链表的相关定义单链表创建一个朴素的单链表#include<iostream>usingnamespacestd;structNode{intval;Node*next;Node(intx):val(x),next(nullptr){}......
  • 揭秘 C++ List 容器背后的实现原理,带你构建自己的双向链表
    本篇博客,我们将详细讲解如何从头实现一个功能齐全且强大的C++List容器,并深入到各个细节。这篇博客将包括每一步的代码实现、解释以及扩展功能的探讨,目标是让初学者也能轻松理解。一、简介1.1、背景介绍在C++中,std::list是一个基于双向链表的容器,允许高效的插入和......