2025/7/20

题目（easy):

---

我的思路：

要判断它是不是回文，那就根据定义，判断首尾对应位置的值是否相同即可。但是链表它不能够进行随机检索。但是我们知道数组可以，所以我们可以把链表的值按顺序复制保存到一个数组当中，然后在这个数组中用索引下标，以双指针的形式来快速判断它是否为回文数

代码如下：

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        #1.把链表变成数组后再进行回文数的判断
        res = []
        p = head

        while p != None:
            res.append(p.val)
            p = p.next

        left,right = 0, len(res)-1
        while left <right:
            if res[left] != res[right]:
                return False
            left += 1
            right -= 1

        return True
        

时间复杂度：O（N）

空间复杂度：O（N）

不过其实在Python里可以快速创建一个数组的反转说是

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        res = []
        p = head

        while p != None:
            res.append(p.val)
            p = p.next
            
        return res == res[::-1]    #直接利用Python的特性，来快速创建一个反转的数组进行比对

时间复杂度：O（N）

空间复杂度：O（N）

这样就简洁很多了

---

优化思路：

考虑只通过常数级别的额外变量来解决这个题目，链表判断回文数的痛点主要是没有随机读取性，也就是没办法直接地进行前后的两两比对。但是鉴于前面学习了如何对链表进行反转，我就想到，那我用一个整数变量去正向相加一遍这个链表，然后把这个链表反转后再遍历相加一遍。如果两次遍历相加的结果相同那不就可以了，看起来时间复杂度O（N)，空间复杂度也只用了两个整形变量去保存正向和反向遍历转为为数字的结果

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        #2.先正着遍历一次计算数字，再反着遍历一次计算数字     
        if head.next == None:
            return True

        #用于遍历的时候迭代反转链表
        pre,cur = head,head.next
        res1 = head.val
        pre.next = None
        i = 10
        #正向遍历计算结果并顺便反转链表
        while cur != None:
            res1 += cur.val* i
            r = cur.next
            cur.next = pre
            pre = cur
            cur = r
            i *= 10

        p = pre
        res2 = 0
        i = 1
        #反向遍历计算结果值
        while p != None:
            res2 += p.val * i
            p = p.next 
            i *= 10
        print(res1,res2)

return res1 == res2    #返回两个结果值的比对

但是运行提交之后我发现自己忽略了一个问题：就是当链表中数字很多的时候，这样子会超出整形变量能保存的数字的上限，即溢出了。因此这个方法实际上是不能解决所有问题的

那既然这样就只能在链表本身上下手了，那既然我们都能够反转整个链表，那可不可以只反转链表的一部分呢？应该是可以的，那我们只要从链表前半部分的结尾之处往后反转，那链表就会被分为前后两部分，然后对这前后两部分同时进行遍历对比即可。那要怎么找到链表一半的位置呢？我们可以通过快慢指针的方式

代码和步骤如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def isPalindrome(self, head: ListNode) -> bool:
        #通过快慢指针找到链表的一半的位置
        if head is None:
            return True

        #1.找到链表前半部分的结尾位置
        fornt_half_end = self.find_EndOf_ForntHalf(head)

        #2.把链表的后半部分进行反转
        back_half_start = self.reverseList(fornt_half_end)

        #3.把前半部分链表和后半部分链表进行比对
        pFornt,pEnd = head,back_half_start
        while pFornt != None and pEnd != None:
            if pFornt.val != pEnd.val:
                #4.把后半部分链表再还原回去
                self.reverseList(fornt_half_end)
                return False
            pFornt = pFornt.next
            pEnd = pEnd.next
        
        #4.把后半部分链表再还原回去
        self.reverseList(fornt_half_end)
        return True       

    def find_EndOf_ForntHalf(self, head:Optional[ListNode]) -> Optional[ListNode]:
        #快慢指针，快指针一次移动两步，慢指针一次移动一步
        slow,fast = head,head
        while slow.next != None and (fast.next != None and fast.next.next != None):
            slow = slow.next
            fast = fast.next.next
        return slow

    def reverseList(self, head:Optional[ListNode])-> Optional[ListNode]:
        #迭代法反转链表
        if head == None or head.next == None:
            return head

        pre,cur = head,head.next
        pre.next = None
        while cur != None:
            r = cur.next
            cur.next = pre
            pre = cur
            cur = r
        return pre

时间复杂度：O（N）

空间复杂度：O（1）

当然是可以最后不用还原反转的部分也行的，但是一般来说我们应该不太会希望自己写的链表被随便更改

---

其他思路：

那还有没有其他方法可以让我们像双指针那样同时比对链表开头和结尾对应部位的元素呢？有的，兄弟，有的。我们就应该想到一种先进后出的数据结构----栈，开头先被压入进去的元素没那么快被访问，而最后压进去的元素会先被弹出进行访问。而与这种栈最相关的一种思路方法其实就是迭代了。

def visitNodeReverse(curNode = head):
            if(curNode is not None):
                visitNodeReverse(curNode.next)
                print(curNode.val)

我们可以这样来优雅地反向遍历链表。由于栈的特性，它会反向打印链表的值

因此我们可以通过递归的特性来实现类似双指针比对的效果了的

代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def isPalindrome(self, head: ListNode) -> bool:
        #通过快慢指针找到链表的一半的位置
        if head is None:
            return True

        self.forntNode = head
        def reverseCheck(curNode = head) -> bool:
            #先把将要遍历的元素都压入栈中，让末尾元素处于栈顶位置
            if curNode is not None:
                #当反转检查值返回是false的时候，就说明回文判断失败了已经，直接一路返回false了
                if not reverseCheck(curNode.next):
                    return False
                #当压入工作完成之后，就进行比对工作，走到这一步可以保证是反向遍历的元素
                if self.forntNode.val != curNode.val:
                    return False
                self.forntNode = self.forntNode.next
            return True

        return reverseCheck()

时间复杂度：O（N）

空间复杂度：O（N）

---

总结：

①单向链表的回文判断的痛点在于不能像数组那样直接用指针指出想要比对的地方进行比对来进行判断。但是可以把它的值保存到数组中，或者通过部分反转的方式，以及递归的方式来实现反向遍历和正向遍历同时进行的操作

②Python中可以快速复制出反转的数组，nums[::-1]

③递归是用堆栈的形式进行的，可以通过它来对一些需要进行后进先出操作的数据进行遍历访问等操作

④快慢指针可以帮助我们遍历得到一个未知长度的链表的中间位置节点