This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

LeetCode 234. Palindrome list Difficulty: Simple (I think not simple…)

1. Title Description

Determine if a linked list is palindromic. Example 1:

Input: 1->2 Output: falseCopy the code

Example 2:

Input: 1->2->2->1 Output: trueCopy the code

Advanced: Can you solve this problem with O(n) time complexity and O(1) space complexity?

Second, train of thought analysis

Said for the convenience of using 3 – > 1 – > 2 – > 2 – > 1 – > 3 – > NULL, for example, for the first node 3, if there is a function that returns 1 – > 2 – > 2 – > 1 – >… If it is a palindrome linked list, and also returns the last node 3, it can determine whether the current linked list is a subroutine. RealIsPalindrome (head) -> bool, Node:, 1->2->2->1->… Will go further to 2->2->… I don’t think I can make it inside. In fact, you can use a length to record the length of the list that the current function should be concerned with, which is easy to determine when the length is 0\1\2, and then the other lengths can be determined recursively. The end result looks like the code.

AC code

    def isPalindrome(self, head: ListNode) - >bool:
        if not head:
            return True

        def lengthOfList(head) :
            p = head
            cnt = 0
            while p:
                p = p.next
                cnt+=1
            return cnt

        def realIsPalindrome(head, length) :
            if length == 1:
                return True, head.next
            if length == 2:
                return head.val == head.next.val, head.next.next
            res, peer = realIsPalindrome(head.next,length-2)        
            if not res or peer is None:
                return False.None
            return head.val == peer.val, peer.next

        length = lengthOfList(head)
        res,_ = realIsPalindrome(head, length )
        return res
Copy the code

Four,

It’s O(1) space, but it’s recursion, and it’s still O(n) stack length.

If you feel good, give me a thumbs-up 💐