Python3实现的判断回文链表算法示例

本文实例讲述了Python3实现的判断回文链表算法。分享给大家供大家参考，具体如下：

问题：

请判断一个链表是否为回文链表。

方案一：指针法

class Solution:
  def isPalindrome(self, head):
    """
    判断一个链表是否是回文的，很自然的想法就是两个指针，一个指针从前往后走，一个指针从后往前走，判断元素值是否相同，这里要分几个步骤来进行求解：
1、找到链表长度的一半，用追赶法，一个指针一次走两步，一个指针一次走一步
2、将后一半数组转置
3、判断链表是否是回文链表
    :type head: ListNode
    :rtype: bool
    """
    slow = fast = head
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
     node = None
    while slow:
      nxt = slow.next
      slow.next = node
      node = slow
      slow = nxt
     while node and head:
      if node.val != head.val:
        return False
      node = node.next
      head = head.next
    return True

方案二：列表法

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, x):
#     self.val = x
#     self.next = None
class Solution:
  def isPalindrome(self, head):
    """
    :type head: ListNode
    :rtype: bool
    """
    res = []
    cur = head
    while cur:
      res.append(cur.val)
      cur = cur.next
    return res == res[: : -1]

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

赞 (0)

相关推荐

  • python算法题 链表反转

    python算法题 链表反转

    链表的反转是一个很常见.很基础的数据结构题,输入一个单向链表,输出逆序反转后的链表,如图:上面的链表转换成下面的链表.实现链表反转有两种方式,一种是循环迭代,另外一种方式是递归. 第一种方式:循坏迭代 循坏迭代算法需要三个临时变量:pre.head.next,临界条件是链表为None或者链表就只有一个节点. # encoding: utf-8 class Node(object): def __init__(self): self.value = None self.next = None de

  • Python实现合并两个有序链表的方法示例

    Python实现合并两个有序链表的方法示例

    本文实例讲述了Python实现合并两个有序链表的方法.分享给大家供大家参考,具体如下: 思路:先选出第一个节点,然后遍历两个链表,把小的作为当前节点的下一个节点,一直到其中一个链表遍历完,这时候把另一个链表直接接上就好 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(obj

  • PHP从尾到头打印链表实例讲解

    题目 输入一个链表,从尾到头打印链表每个节点的值. 题解 一种是使用栈. 第二种是递归. 代码 //递归版本 function printListFromTailToHead($head) { if($head == NULL){ return []; } $arr = array(); $cur = $head; if($cur->next != null){ $arr = printListFromTailToHead($cur->next); } array_push($arr, $cu

  • 基于python实现从尾到头打印链表

    这篇文章主要介绍了基于python实现从尾到头打印链表,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 题目描述 输入一个链表,按链表从尾到头的顺序返回一个ArrayList. 思路 遍历链表,把结构保存在list里面,然后把list逆序输出 代码 # -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None

  • 对python实现合并两个排序链表的方法详解

    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 1.迭代方法 def Merge(self, pHead1, pHead2): p1, p2 = pHead1, pHead2 if p1 and p2: if p1.val < p2.val: head = p1 p1 = p1.next else: head = p2 p2 = p2.next cur = head elif p1: return p1 else: return p2 while p

  • C++实现打印两个有序链表公共部分的方法

    本文实例讲述了C++实现打印两个有序链表公共部分的方法.分享给大家供大家参考,具体如下: 题目: 给定两个有序链表的头指针head1和head2,打印两个链表的公共部分. 解题思路及代码: 1.head1的值小于head2,则head1往下移动 2.head1的值小于head2,则head2往下移动 3.相等则打印任何一个链表节点的值,head1和head2都往下移动. 4.当head1或head2移动到NULL,终止. 算法C++代码: typedef struct Node { int da

  • c语言链表基本操作(带有创建链表 删除 打印 插入)

    复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <malloc.h>#define LEN sizeof(struct Student)struct Student{    long num;    float score;    struct Student*next;};int n;int main(){    /*-----------------------------程序描述----------

  • Java编程实现从尾到头打印链表代码实例

    问题描述:输入一个链表的头结点,从尾巴到头反过来打印出每个结点的值. 首先定义链表结点 public class ListNode { int val; ListNode next = null; ListNode(int val){ this.val = val; } } 思路1:此题明显想到是利用栈的思想,后进先出,先遍历链表,依次将结点值进栈.最后在遍历栈出栈. public static Stack<Integer> printListReverse_Stack(ListNode li

  • 面试题:用 Java 逆序打印链表

    昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 volatile 关键字,不少朋友问我,到底为啥要加 volatile 这个关键字呀,而它,到底又有什么神奇的作用呢? 对 volatile 这个关键字,在昨天的讲解中我们简单说了一下:被 volatile 修饰的共享变量,都会具有下面两个属性: 保证不同线程对该变量操作的内存可见性. 禁止指令重排序. 共享变量:如果一个变量在多个线程的工作内存中都存在副本,那么这个变量就是这几个线程的共享变量. 可见性:一个线

  • Python3实现的判断回文链表算法示例

    本文实例讲述了Python3实现的判断回文链表算法.分享给大家供大家参考,具体如下: 问题: 请判断一个链表是否为回文链表. 方案一:指针法 class Solution: def isPalindrome(self, head): """ 判断一个链表是否是回文的,很自然的想法就是两个指针,一个指针从前往后走,一个指针从后往前走,判断元素值是否相同,这里要分几个步骤来进行求解: 1.找到链表长度的一半,用追赶法,一个指针一次走两步,一个指针一次走一步 2.将后一半数组转置

  • Python判断回文链表的方法

    Python判断回文链表的方法

    什么是回文数? 回文数简单的说就是正着倒着读都是一样的,比如:12321,1221,1111等等,正着读也是12321,倒着读也是12321. 首先,接收用户输入数字列表转换成链表 比如用户输入:1 2 3 2 1,转换为链表后,如下图 首先接收用户输入数字列表,每个数字用空格分隔,使用split截断字符串,使用map,把每个元素映射成int类型,然后再转成list,使用循环取出每项元素添加到链表中. lt = list(map(int, s.split(' '))) 代码如下: # 链表类 c

  • Python3最长回文子串算法示例

    本文实例讲述了Python3最长回文子串算法.分享给大家供大家参考,具体如下: 1. 暴力法 思路:对每一个子串判断是否回文 class Solution: def longestPalindrome(self, s): """ :type s: str :rtype: str """ if len(s) == 1: return s re = s[0] for i in range(0,len(s)-1): for j in range(i+1

  • Python实现判断一个整数是否为回文数算法示例

    Python实现判断一个整数是否为回文数算法示例

    本文实例讲述了Python实现判断一个整数是否为回文数算法.分享给大家供大家参考,具体如下: 第一个思路是先将整数转换为字符串,再将字符串翻转并与原字符串做比较 def isPalindrome(self, x): """ :type x: int :rtype: bool """ #思路:先将整数转换为字符串,再将字符串翻转并与原字符串做比较 x = str(x) return x == x[::-1] 代码简洁 第二个思路,尝试着不用字符串,

  • 带你粗略了解C++回文链表

    带你粗略了解C++回文链表

    目录 请判断一个链表是否为回文链表. 思路 总结 请判断一个链表是否为回文链表. 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 思路 1.用快慢指针,快指针有两步,慢指针走一步,快指针遇到终止位置时,慢指针就在链表中间位置 2.同时用pre记录慢指针指向节点的前一个节点,用来分割链表 3.将链表分为前后均等两部分,如果链表长度是奇数,那么后半部分多一个节点 4.将后半部分反转 ,得cur2,前半部分为cur1 5.按照

  • Python实现常见的回文字符串算法

    回文 利用python 自带的翻转 函数 reversed() def is_plalindrome(string): return string == ''.join(list(reversed(string)))` 自己实现 def is_plalindrome(string): string = list(string) length = len(string) left = 0 right = length - 1 while left < right: if string[left]

  • javascript判断回文数详解及实现代码

    javascript判断回文数 概要: 回文"是指正读反读都能读通的句子,它是古今中外都有的一种修辞方式和文字游戏,如"我为人人,人人为我"等.在数学中也有这样一类数字有这样的特征,成为回文数(palindrome number). 设n是一任意自然数.若将n的各位数字反向排列所得自然数n1与n相等,则称n为一回文数.例如,若n=1234321,则称n为一回文数:但若n=1234567,则n不是回文数. 注意: 1.偶数个的数字也有回文数124421     2.小数没有回文

  • Python判断回文数的三种方法实例

    需求: 从控制台输入一个五位数,如果是回文数就打印"是回文数",否则打印"不是回文数",例如:11111 12321 12221 "回文"是指正读反读都能读通的句子,它是古今中外都有的一种修辞方式和文字游戏,如"我为人人,人人为我"等.在数学中也有这样一类数字有这样的特征,成为回文数(palindrome number). 设n是一任意自然数.若将n的各位数字反向排列所得自然数n1与n相等,则称n为一回文数.例如,若n=123

  • Python3实现的判断环形链表算法示例

    本文实例讲述了Python3实现的判断环形链表算法.分享给大家供大家参考,具体如下: 给定一个链表,判断链表中是否有环. 方案一:快慢指针遍历,若出现相等的情况,说明有环 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def hasCycle(self,

  • python最长回文串算法

    给定一个字符串,要求在这个字符串中找到符合回文性质的最长子串.所谓回文性是指诸如 "aba","ababa","abba"这类的字符串,当然单个字符以及两个相邻相同字符也满足回文性质. 看到这个问题,最先想到的解决方法自然是暴力枚举,通过枚举字符串所有字串的起点,逐一判断满足回文性的子串,记录长度并更新最长长度.显然这种算法的时间复杂度是很高的,最坏情况可以达到O(N*N).所以呢,这里提出一个优化的方案,通过枚举字符串子串的中心而不是起点,向两

随机推荐