LeetCode 234. 回文链表 Palindrome Linked List
Table of Contents
一、中文版
请判断一个链表是否为回文链表。
示例 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] 即可。
