<LeetCode天梯>Day028 回文链表(双指针+递归+栈+数组) | 初级算法 | Python

2021年11月20日 阅读数:3
这篇文章主要向大家介绍<LeetCode天梯>Day028 回文链表(双指针+递归+栈+数组) | 初级算法 | Python,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

💖做者简介:你们好,我是车神哥,府学路18号的车神🥇html

📝我的主页:应无所住而生其心的博客_府学路18号车神_CSDN博客
🎉点赞评论收藏 == 养成习惯(一键三连)😋
📖本系列主要以刷LeetCode力扣)网站的各种题为标准,实现自我能力的提高为目标⚡
⚡但愿你们多多支持🤗~一块儿加油 😁node

周四,今天中午终于拥有了一个久违的午休了,老黄说我睡到打呼噜,连续加班几天了,赶项目,作实验,写论文,哎,对了,官方送的CSDN的水杯到了,应该是C站人手一个吧,哈哈哈,一杯茶,坐下就是一下午,加油吧!python

天天进步一点点,就已经很棒很棒了,坚持坚持,不要太累,拒绝内卷,从每日一练开始,天天十分钟,快乐生活一生!疫情依旧反复,你们带好口罩啊~ 继续继续,来,今天和车神哥一块儿来提高本身的Python编程面试能力吧,刷天梯~web

放上我拍的Photo吧!~面试

在这里插入图片描述

每日推荐一首歌:夏天的风——火羊瞌睡了算法

如下为个人天梯积分规则编程

每日至少一题:一题积分+10分
若多作了一题(或多一种方法解答),则当日积分+20分(+10+10)
若作了三道以上,则从第三题开始算+20分(如:作了三道题则积分-10+10+20=40;作了四道题则积分–10+10+20+20=60数组


初始分为100分
若差一天没作题,则扣积分-10分(周6、周日除外注:休息
坚持!!!app


初级算法

刷题目录

链表

在这里插入图片描述

题干

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。若是是,返回 true ;不然,返回 false 。svg

示例1:
在这里插入图片描述

:head = [1,2,2,1]
输出:true

示例2:
在这里插入图片描述

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

提示:

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

双指针(反转后半部分链表)

分析:

首先要明白一点回文链表是什么,回文链表就是以链表中间为中心点两边对称
平时比较常见的是字符串回文串,咱们使用双指针,一直指向首,另外一个指向尾部,这样往中间一直走一直比对,所有相同则返回True,不一样则False。
因为本题判断的是链表,且是单向链表,只能从前日后访问,不能从后往前访问,因此使用判断字符串的那种方式是行不通的。
可是咱们能够经过首先寻找到中间的节点,而后再将后半部分节点进行反转操做,再将两半部分链表进行比对就OK了。

具体的借用下大佬的图:

在这里插入图片描述
在这里插入图片描述

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # 双指针
        fast = head
        slow = head

        if not head or not head.next:
            return True

        # 若fast不为空值,则链表的长度为奇数
        # if fast != None:
        #     slow = slow.next

        # 反转后半部分链表
        def reversenode(head):
            out = None
            while head:
                next = head.next
                head.next = out
                out = head
                head = next
            return out
        
        # 经过快慢指针找到中点
        while fast  and fast.next:
            fast = fast.next.next
            slow = slow.next

        slow = reversenode(slow)
        # fast = head
        while slow and head:
            # 依次比较节点值是否相同
            if head.val != slow.val:
                return False
            # else:
            head = head.next
            slow = slow.next
        return True

真的,真的,真的好慢呀!~
在这里插入图片描述

递归法

再试试递归法~

能够对链表逆序操做:

def reverseListNode(head):
	if head == None:
		return  # 终止条件
	pre = None
	pre = reverseListNode(head.next)
	return pre

引用一下官方的代码(主要是较为优雅),直接上代码:

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
       # 递归

        self.front_pointer = head

        def re_check(current_node=head):
            if current_node is not None:
                if not re_check(current_node.next):
                    return False
                if self.front_pointer.val != current_node.val: # 比较
                    return False
                self.front_pointer = self.front_pointer.next
            return True

        return re_check()

说实话,这个递归更慢,下面再试一下栈!递归有点难以理解,建议慢慢思考!~

在这里插入图片描述

利用先进后出的思想,将其放在栈中,而后再一个一个出站,就实现了链表从后往前访问了。

其中还能够用一个简单的,将链表的值放在list中,再对数组进行反转,再比对反转后有无相同。

先实现栈操做:

遍历链表,把每一个节点都Push进stack中;而后再遍历链表,同时节点依次出栈,两者进行比较。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
 		stack = []
        # Push 操做
        current_node = head
        while current_node:
            stack.append(current_node)
            current_node = current_node.next
        # POP + Compare 删除和比较
        node = head
        while stack:
            node2 = stack.pop()  # 删除最后一个,将其删除值赋值给node2
            if node.val != node2.val:
                return False
            node = node.next
        return True

利用栈操做,比递归快不少,哈哈哈!
在这里插入图片描述

链表转数组比对

接着上面的,咱们能够将链表值直接存入新的数组中,而后再对数组反转,将两者进行比对,若是相同则True,不然False。

这思想好像是最简单的了!!!

哈哈哈

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
  		# 数组
        sav = []             # 设置空list
        while head:         # 存入list
            sav.append(head.val)
            head = head.next
        return sav == sav[::-1]

速度又提高了耶!~

在这里插入图片描述
今天用了四种方法,加油呀!!

准备又要开始作论文实验了o(╥﹏╥)o,谁来帮帮我呀!~

Reference

做者:力扣 (LeetCode)
连接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnarn7/
来源:力扣(LeetCode)


今日得分:+10+10+20+20
总得分:590

加油!!!

❤坚持读Paper,坚持作笔记,坚持学习,坚持刷力扣LeetCode❤!!!
坚持刷题!!!打天梯!!!
To Be No.1

⚡⚡


创做不易⚡,过路能❤关注收藏点个赞三连就最好不过了

ღ( ´・ᴗ・` )


我历来不相信什么懒洋洋的自由,我向往的自由是经过勤奋和努力实现的更广阔的人生,那样的自由才是珍贵的、有价值的;我相信一万小时定律,我历来不相信天上掉馅饼的灵感和坐等的成就。作一个自由又自律的人,靠势必实现的决心认真地活着。