6/2 每日一題(檢查鍊表是否回文)

 Given the head of a singly linked list, return true if it is a 

palindrome

 or false otherwise.

 

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

 

Constraints:

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

 

Follow up: Could you do it in O(n) time and O(1) space?

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, val=0, next=None):

#         self.val = val

#         self.next = next

class Solution:

    def isPalindrome(self, head: Optional[ListNode]) -> bool:

        #空或單節點直接返回True

        if not head or not head.next:

            return True

        #使用stack

        stack=[] #初始化stack

        cur = head

        """把每個節點的值放入stack ,之後利用pop()從後端與鏈結的前端依序比較節點的值"""

       

        while cur:

           

            stack.append(cur.val)

            cur=cur.next

        #head 依序遍歷的節點會是   1 -> 2 -> 2 -> 1   也就是左指針

        #stack=[1,2,2,1] , 依序使用pop()得到的值會從末端開始,也就是右指針 會是 1,2,2,1

        while head:

            if head.val != stack.pop():

                return False

            head=head.next

        return True