判断一个链表是否为回文结构

判断一个链表是否为回文结构_牛客题霸_牛客网

问题简述

给定一个链表，请判断该链表是否为回文结构。

思路1：可以使用额外空间

Python 写法1：递归

class Solution:
    def isPail(self , head: ListNode) -> bool:
        import sys
        sys.setrecursionlimit(1000001)
        
        self.forward = head
        
        def dfs(backward):
            if not backward: 
                return True
            r1 = dfs(backward.next)
            r2 = backward.val == self.forward.val
            self.forward = self.forward.next
            return r1 and r2
        
        return dfs(head)

Python 写法2：列表

class Solution:
    def isPail(self , head: ListNode) -> bool:
        
        tmp = []
        cur = head
        while cur:
            tmp.append(cur.val)
            cur = cur.next
        
        N = len(tmp)
        return all(tmp[i] == tmp[N - 1 - i] for i in range(N // 2))  # all([]) == True

思路2：不使用额外空间

• 使用快慢指针，找到链表中点；

• 对中点逆序后比较；

Python

class Solution:
    def isPail(self , head: ListNode) -> bool:
        
        # 初始化 f = head.next，这样结束时 s 刚好在中点的前一个节点
        s, f = head, head.next
        while f and f.next:
            s = s.next
            f = f.next.next

        pre, cur = None, s.next
        s.next = None  # 从中点断开，这一步在本题不是必须的，但建议写上
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        
        l, r = head, pre
        while r:
            if l.val != r.val:
                return False
            l = l.next
            r = r.next
        
        return True