LeetCode 234. Palindrome linked list

The title

Determine if a linked list is palindromic.

Example 1: Input: 1->2 Output:falseExample 2: Input: 1->2->2->1 Output:true
Copy the code

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

Their thinking

# 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: ListNode) -> bool:
        # tempList = []
        # while head ! = None:
        # tempList.append(head.val)
        # head = head.next
        # if tempList[:] == tempList[::-1]:
        # return True
        # return False
        Fast pointer to the end, slow pointer just to the middle, and then reverse the slow pointer before, and then compare the two sides, pay attention to the difference between odd and even
        left = right = head
        pre = None
        ret = True
        while right and right.next:
            right = right.next.next
            # reverse the link where the slow pointer goes
            tempCur = left.next
            left.next = pre
            pre = left
            left = tempCur
        RHead = left # Reverse the intersection of the link and the original header, used for restoring the original state when the lap
        # the even
        if right == None:
            right = left
            left = pre
        # odd
        elif right.next == None:
            right = left.next
            left = pre
        while right and left:
            if right.val == left.val:
                right = right.next
                left = left.next
            else:
                ret = False
                break
        # Restore the reverse link
        left = pre
        pre = RHead
        while left:
            tempCur = left.next
            left.next = pre
            pre = left
            left = tempCur
        return ret

if __name__ == '__main__':
    # linked list sample
    #L1 1->2->3->4->5
    l1 = ListNode(1,ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    #L2 1->3->4
    l2 = ListNode(1, ListNode(3, ListNode(4)))
    ret = Solution().isPalindrome(l1)
    print(ret)
    # print(ret.val)
    # print(ret.next.val)
    # print(ret.next.next.val)
    # print(ret.next.next.next.val)
    # print(ret.next.next.next.next.val)
Copy the code