requirements

Give you a single linked list of the head node head, please determine whether the list is a palindrome list. If so, return true; Otherwise, return false.

Example 1:

Input: head = [1,2,2,1] output: trueCopy the code

Example 2:

Input: head = [1,2] output: falseCopy the code

Tip:

  • The number of nodes in the linked list is in the range [1, 105]
  • 0 <= Node.val <= 9

 

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

The core code

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 or head.next is None:
            return True
        l = []
        p = head
        while p.next:
            l.append(p.val)
            p = p.next
        l.append(p.val)
        return l == l[::-1]
Copy the code

Another solution

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 or head.next is None:
            return True
        if head.next.next is None:
            return head.val == head.next.val
        fast = slow = q = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        def reverse_list(head) :
            if head is None:
                return head
            cur = head
            pre = None
            nxt = cur.next
            while nxt:
                cur.next = pre
                pre = cur
                cur = nxt
                nxt = nxt.next
            cur.next = pre
            return cur
        p = reverse_list(slow.next)
        while p.next:
            ifp.val ! = q.val:return False
            p = p.next
            q = q.next
        return p.val == q.val
Copy the code

First solution: we use a list to store the data, and then we reverse the list to see if the data after the inversion is the same as the previous data. If the same data is the palindrome linked list, otherwise it is not. The second solution: we use the fast and slow pointer. When our FAST moves to the end, our slow happens to be in the center. We reverse the nodes of slow.