python - Python链表无法保存头节点
问题描述
这是关于一个leetcode问题:“234. Palindrome Linked List”
我想反转链接列表并将反转的列表与原始列表进行比较。如果没有区别,则返回 True。
但奇怪的是,虽然我将 head 复制到了一个虚拟节点,来记录起始位置。反转列表后,我无法从虚拟节点迭代,似乎列表中只剩下 1 个元素。
为什么/如何更新虚拟节点?这让我很难受,我想把头撞到墙上。
任何帮助表示赞赏!
谢谢!
根据我有限的知识,我已经尝试了所有我能做的事情。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
dummy = head
prev = None
while head:
temp = head
head = head.next
temp.next = prev
prev = temp
while prev and dummy:
print prev.val, dummy.val
if prev.val != dummy.val:
return False
prev = prev.next
dummy = dummy.next
return True
我希望上面的代码能够正常工作
解决方案
从您的代码中,我认为您的想法是反向链接列表,并与原始链接列表进行比较,但这样做是不正确的。因为你改变了原来的链表,你不能再做比较,所以你必须复制,但这是一个低效的解决方案。
我copy version
根据您的代码进行了编辑,它可以工作,但这不是最好的方法。
def isPalindrome(self, head):
dummy = head
prev = None
cur = origin = ListNode(0)
# copy the original linkedlist
while head:
cur.next = ListNode(head.val)
head = head.next
cur = cur.next
head = dummy
while head:
temp = head
head = head.next
temp.next = prev
prev = temp
cur = origin.next
while prev and cur:
print(prev.val, cur.val)
if prev.val != cur.val:
return False
prev = prev.next
cur = cur.next
return True
更好的做法是反转 LinkList 的前半部分,并比较前半部分是否等于后半部分:
def isPalindrome(self, head):
if not head or not head.next:
return True
count, cur = 0, head
while cur:
cur = cur.next
count += 1
pre, cur, post = None, head, head.next
for _ in range(count // 2):
cur.next = pre
pre, cur, post = cur, post, post.next
head.next = cur
slow = pre
fast = cur.next if count % 2 else cur
for _ in range(count // 2):
if slow.val != fast.val:
return False
slow, fast = slow.next, fast.next
return True
更优雅的版本,但不是那么容易理解:
def isPalindrome(self, head):
check = None
slow = fast = head
# traverse and reverse
while fast and fast.next:
fast = fast.next.next
check, check.next, slow = slow, check, slow.next
if fast:
slow = slow.next
while slow and slow.val == check.val:
slow = slow.next
check = check.next
return not check
希望对您有所帮助,如果您还有其他问题,请发表评论。:)
推荐阅读
- sql - 基于值而不是计数的 ntile 函数
- java - 如何修复 application.yml 文件中的解析异常?
- wordpress - 获取WordPress中特定页面的最后修改日期
- java - 标记为只读的 PDComboBox 在 PDF 文档中不可见
- parallel-processing - 来自 RevoScaleR 的 rxExec 不会发生并行处理
- php - 如何在 Wordpress 模板上修复移动屏幕底部的按钮
- docusignapi - Dosusign API 访问令牌延长到期
- c# - For 循环增加文本框 ID。C# Windows 窗体
- ecmascript-5 - 在我的 tsconfig 中使用 es2017 作为库但将 es5 作为我的目标会使我的代码与 IE11 不兼容吗?
- python - 为什么在python类中设置方法在调用时不传递self?