乐趣区

关于数据结构与算法:每日leetcode234-回文链表

题目

给你一个单链表的头节点 head,请你判断该链表是否为回文链表。如果是,返回 true;否则,返回 false。

进阶:你是否用 O(n) 工夫复杂度和 O(1) 空间复杂度解决此题?

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


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

思路

第一个想到的就是,间接把整个链表翻转,而后和原来的链表比拟。
然而题目要求工夫复杂度 O(n),空间复杂度 O(1),这个思路要保留翻转后的链表,空间复杂度首先就不满足了。

满足复杂度的思路如下:

  1. 将链表从两头一分为二
    应用快慢指针,slow 每次挪动 1 个节点,fast 每次挪动 2 个节点。当 fast 挪动到开端,无奈继续前进 2 个节点时,slow 所在的节点就是链表的两头地位。
  2. 将右半局部链表翻转
  3. 遍历左、右两个链表的每个节点,看每个节点的值是否雷同
def isPalindrome(self, head: ListNode) -> bool:
        # 初始化快慢指针
        slow = fast = head

        # 遍历链表,挪动快慢指针,切分链表
        # 当 fast 挪动到尾节点或尾节点的前一个节点时,下一次无奈挪动 2 个节点,则遍历实现
        # 此时 slow 指针指向了链表的两头地位
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # 翻转右半局部链表
        # 在翻转后的右半局部链表头节点设置 rightHead 指针
        rightHead = self.reverseList(slow.next)

        # 在左半局部链表头节点设置 leftHead 指针
        leftHead = head

        # 以遍历右半局部链表为准,因为切分链表的时候,如果链表节点个数是奇数,左半局部会多 1 个节点
        while rightHead:
            # 如果有节点的值不同,就不是回文链表,返回 False
            if leftHead.val != rightHead.val:
                return False
            # 挪动指针
            leftHead = leftHead.next
            rightHead = rightHead.next
            
        # 遍历完结,节点的值都雷同,是回文链表,返回 True
        return True
        
    def reverseList(self,head):
        if head==None or head.next==None:
            return head

        tmp = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return tmp
退出移动版