我的链接列表是基于我的解决方案的回文吗？

Question

我编写了以下代码来确定我的链接列表是否为回文。 我采取的步骤是：

1. 计算链表中的节点数，找到中点并将链表分成两半
2. 反转链接列表的后半部分
3. 比较链接列表上半部分和下半部分的每个节点，以确定是否有回文
4. 重新反转链接列表的后半部分

def isPalindrome(self, head: ListNode) -> bool:

    if head == None:
        return True

    #Finding the number of nodes in my linked list
    length_ll = 0
    curr = head
    while curr:
        length_ll +=1
        curr = curr.next

    #initializing head2 to be the midpoint node in the linked list
    mid_point = len(length_ll)//2
    
    #reversing second half of linked list
    head2 = mid_point + 1.  #Can I write this line?
    prev = head2
    curr = head2
    nex = head2.next

    while nex:
        curr = nex
        curr.next = prev
        nex = nex.next
        prev = curr
    head2.next = None

    #comparing nodes of first and second half of linked list to determine if LL is a palindrome
    curr = head
    curr2 = head2
    while curr2:
        if curr2.val != curr.val:
            return False

我有两个问题：

1. 在我的代码中，我注释了一个问题“我可以写这行吗？”？我的问题是我是否可以简单地初始化head2作为链接列表的中点节点。如果没有，我怎么做
2. 如何重新反转链接列表的后半部分

Answer 1

所以@shorya sharma的道具他们的解决方案肯定是一条路要走

也就是说直接回答你的问题。不，您不能添加该行。 问题是中点是一个整数，头2必须是一个ListNode

相反，将该行替换为：

midpoint = length_ll // 2 # length_ll is already an integer, no need to call len
head2 = head
for _ in range(midpoint):
    head2 = head2.next

我是这里的新手，所以请告诉我是否禁止发布其他网站的链接

您将在此处找到有关如何解决此问题的详细讨论：https://leetcode.com/problems/palindrome-linked-list/discuss/?currentPage=1&orderBy=most_votes&query=