LeetCode 234. Palindrome Linked List

Description

https://leetcode.com/problems/palindrome-linked-list/

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

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

Explanation

A palindrome, and its reverse, are identical to each other.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:

        reversed_head = self.reverse(head)

        while (head != None and reversed_head != None):

            if (head.val != reversed_head.val):
                return False
            
            head = head.next
            reversed_head = reversed_head.next
        
        return True
    
    def reverse(self, head):        
        prev = None
                
        dummy = ListNode(0)
        dummy.next = head
        current = head
                
        while (current != None):
            new = ListNode(current.val)
            new.next = prev
            prev = new
            current = current.next
        
        head = dummy.next
        
        return prev
        

• Time complexity: O(N).
• Space complexity: O(1).