英文:
Check if the Linked List is Palindrome or not
问题
以下是你要翻译的代码部分:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverseLL(head):
if head is None or head.next is None:
return head
rest = reverseLL(head.next)
head.next.next = head
head.next = None
return rest
def checkpalindrome(head):
temp = reverseLL(head)
while head != None and temp != None:
if temp.data != head.data:
return False
temp = temp.next
head = head.next
return True
英文:
When I try to check whether the linked list is palindrome or not, the following code gives me the error. My Approach is:
Step 1:- I am reversing the linked list (temp = reverseLL(head).
Step 2:- Checking elements of the reverse linked list to the original linked list.
Step 3:- Returning True if it is palindrome else False
But my code is not working for the input [1,1,2,1], it shows me the result is True.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverseLL(head):
if head is None or head.next is None:
return head
rest = reverseLL(head.next)
head.next.next = head
head.next = None
return rest
def checkpalindrome(head):
temp = reverseLL(head)
while head != None and temp != None:
if temp.data != head.data:
return False
temp = temp.next
head = head.next
return True
答案1
得分: 0
你可以将链表中的值创建成一个普通列表,然后将该列表与其反转版本进行比较。类似这样:
class Node:
def __init__(self, n, next=None):
self.n = n
self.next = next
nums = [[1, 1, 2, 1, 1], [1, 1, 2, 1]]
def populate(nums):
if nums:
head = Node(nums[0])
tail = head
for n in nums[1:]:
tail.next = Node(n)
tail = tail.next
return head
return None
def ispalindrome(head):
if head:
values = [head.n]
while head := head.next:
values.append(head.n)
return values == values[::-1]
return False
for nl in nums:
head = populate(nl)
if ispalindrome(head):
print(nl, 'is palindromic')
else:
print(nl, 'is not palindromic')
输出结果:
[1, 1, 2, 1, 1] is palindromic
[1, 1, 2, 1] is not palindromic
英文:
You could create a regular list out of the values in the linked list then simply compare that list with a reversed version of itself. Something like this:
class Node:
def __init__(self, n, next=None):
self.n = n
self.next = next
nums = [[1, 1, 2, 1, 1], [1, 1, 2, 1]]
def populate(nums):
if nums:
head = Node(nums[0])
tail = head
for n in nums[1:]:
tail.next = Node(n)
tail = tail.next
return head
return None
def ispalindrome(head):
if head:
values = [head.n]
while head := head.next:
values.append(head.n)
return values == values[::-1]
return False
for nl in nums:
head = populate(nl)
if ispalindrome(head):
print(nl, 'is palindromic')
else:
print(nl, 'is not palindromic')
Output:
[1, 1, 2, 1, 1] is palindromic
[1, 1, 2, 1] is not palindromic
答案2
得分: 0
问题是,当列表被反转时,head
节点变成了尾部,因此回文检查将比较反转后的列表与其自身的尾节点(该尾节点没有下一个节点)。
请注意,反转的列表并不创建一个新的列表。它只是将原始列表反转,因此没有更多的可能性以原始顺序遍历列表。
一个不需要 O(n) 辅助空间的解决方案是只反转列表的一半,然后您可以比较这两个部分。
以下是如何调整您的代码来实现这一点:
def checkpalindrome(head):
return isPrefixLL(head, reverseLL(centerLL(head)))
def centerLL(head): # 检索中间节点(或第二半的第一个节点)
fast = slow = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def isPrefixLL(a, b): # 这是您已经拥有的比较代码
while a and b:
if a.data != b.data:
return False
a = a.next
b = b.next
return True
您的 reverseLL
代码可以保持不变,尽管它使用了额外的堆栈空间。如果您真的想避免 O(n) 辅助空间,您应该将其改为迭代版本,这样也会运行得稍快一些:
def reverseLL(head):
tail = None
while head:
head.next, tail, head = tail, head, head.next
return tail
英文:
The problem is that when the list has been reversed, the head
node has become the tail, and so the palindrome check will compare the reversed list with its own tail node (that has no next node).
Realise that the reversed list does not create a new list. It is the original list that has been reversed and so there is no more possibility to traverse the list in its original order.
A solution that does not need O(n) auxiliary space is to only reverse half of the list and then you can compare the two halves.
Here is how your code could be adapted to achieve that:
def checkpalindrome(head):
return isPrefixLL(head, reverseLL(centerLL(head)))
def centerLL(head): # Retrieve the middle node (or the first of second half)
fast = slow = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def isPrefixLL(a, b): # This is the comparison code you already had
while a and b:
if a.data != b.data:
return False
a = a.next
b = b.next
return True
Your reverseLL
code can remain unchanged, although it uses extra stack space. If you really want to avoid O(n) auxiliary space, you should make it iterative -- which will also run slightly faster:
def reverseLL(head):
tail = None
while head:
head.next, tail, head = tail, head, head.next
return tail
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论