LeetCode 234. 回文链表 Palindrome Linked List

简介: LeetCode 234. 回文链表 Palindrome Linked List

LeetCode 234. 回文链表 Palindrome Linked List


Table of Contents

一、中文版

二、英文版

三、My answer

四、解题报告


一、中文版

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

示例 1:

输入: 1->2

输出: false

示例 2:

输入: 1->2->2->1

输出: true

进阶:

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?


二、英文版

Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


三、My answer

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if head == None:
            return True
        # 1、复制链表 head 为 head1  
        # dummy、dummy1 不断后移,head、head1 不动
        head1 = ListNode(head.val)
        dummy1 = head1
        dummy = head
        while dummy != None and dummy.next != None:
            dummy1.next = ListNode(dummy.next.val)
            dummy = dummy.next
            dummy1 = dummy1.next
#         print('dummy',dummy)
#         print('head',head)
#         print('dummy1',dummy1)
#         print('head1',head1)
        # 2、翻转head1      
        cur = head1
        prev = None
        while head1 != None:
            temp = head1.next
            head1.next = prev
            prev = head1
            head1 = temp
        # 3、比较 head 与 head1 是否一样      
        while head != None:
            if head.val != prev.val:
                return False
            head = head.next
            prev = prev.next
        return True


四、解题报告

我的想法比较简单 —— 利用经典题目 “翻转链表”的思想:

1、复制原链表 head 到一个新链表 head1

2、翻转新链表 head1

3、挨个节点比较 head 和 翻转后的 head1,如果有一个不一样,就返回 False;能比较到最后则返回 True。

注意:

复制链表时,不能直接写 head1 = head,因为这只是复制了引用,相当于两个指针 (head、 head1)指向同一个节点。

 

法二:

1、遍历一遍链表,把每个节点的值存入数组(列表)里,

2、再比较数组是否是回文, Python 中有个翻转数组的方法 value_list[::-1],所以只要判断 value_list 是否等于 value_list[::-1] 即可。

相关文章
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
【数据结构】环形、相交、回文、分割、合并、反转链表
【数据结构】环形、相交、回文、分割、合并、反转链表
289 1
【刷题记录】链表的回文结构
【刷题记录】链表的回文结构
242 1
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
327 0
【数据结构OJ题】链表的回文结构
|
存储 C++
C++的list-map链表与映射表
```markdown C++ 中的`list`和`map`提供链表和映射表功能。`list`是双向链表,支持头尾插入删除(`push_front/push_back/pop_front/pop_back`),迭代器遍历及任意位置插入删除。`map`是键值对集合,自动按键排序,支持直接通过键来添加、修改和删除元素。两者均能使用范围for循环遍历,`map`的`count`函数用于统计键值出现次数。 ```
400 1
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
存储 C++
C++的list-map链表与映射表
这篇教程介绍了C++中`list`链表和`map`映射表的基本使用。`list`链表可通过`push_front()`、`push_back()`、`pop_front()`和`pop_back()`进行元素的添加和删除,使用迭代器遍历并支持在任意位置插入或删除元素。`map`是一个键值对的集合,元素自动按键值排序,可使用下标操作符或`insert()`函数插入元素,通过迭代器遍历并修改键值对,同时提供`count()`方法统计键值出现次数。教程中包含多个示例代码以帮助理解和学习。
458 2
|
Python
【Leetcode刷题Python】234.回文链表
两种判断链表是否为回文的方法:使用栈和拆分为两个链表后反转对比,并给出了相应的Python代码实现。
370 0
|
算法 C语言
【数据结构与算法 经典例题】链表的回文结构(图文详解)
【数据结构与算法 经典例题】链表的回文结构(图文详解)
|
C++ 容器
【C++进阶】深入STL之list:高效双向链表的使用技巧
【C++进阶】深入STL之list:高效双向链表的使用技巧