当前位置：首页 > article >正文

【hot100】刷题记录(12)-回文链表

article 2025/2/4 23:05:59

题目描述：

给你一个单链表的头节点 head ，请你判断该链表是否为

回文链表

。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

我的作答：

我的思路是先复制一个一样的链表，再反转这个复制的链表，一个结点一个结点比较，碰到不一样的就return false

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: bool
        """
        if not head: return True
        def copylist(head): #复制链表
            dummy = ListNode(0)
            cur = dummy
            while head:
                cur.next = ListNode(head.val)
                cur = cur.next
                head = head.next
            return dummy.next #这个头结点真的好烦
        def reverse(copy_head): #反转复制的链表
            cur, pre = copy_head, None
            while cur:
                temp = cur.next
                cur.next = pre
                pre = cur
                cur = temp
            return pre
        copy_head = copylist(head)
        copy_head = reverse(copy_head)
        cur1, cur2 = head, copy_head
        while cur1 and cur2: #比较
            if cur1.val!=cur2.val:
                return False
            cur1 = cur1.next
            cur2 = cur2.next
        return True

缺点是真的很繁琐。。orz

参考：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: bool
        """
        # 保证长度大于1，方便一刀两段
        if not head.next: return True

        # 遍历一遍得长度
        # -------------
        l = 0
        cur = head
        while cur:
            cur = cur.next
            l += 1
        # ---------------
        

        # 根据长度反转前面一半的链表
        # -------------------------
        pre = None
        cur = head
        i = 0
        while l//2 != i:
            nxt =cur.next
            cur.next = pre
            pre = cur
            cur = nxt
            i += 1
        # -----------------------
        # 长度为奇数，中间的数不用比较
        if l % 2 == 1: cur = cur.next


        # 一一对照即可
        while cur and pre:
            if cur.val != pre.val:
                return False
            cur = cur.next
            pre = pre.next
        return True