Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# = next
class Solution:
Optimal solution with O(1) space
step1: find mid node
step2: reverse mid node to the end
step3: compare the first and second half nodes
def isPalindrome(self, head: ListNode) -> bool:
nums = []
cur = head
while cur:
cur =
return nums==nums[::-1]
def isPalindrome(self, head: ListNode) -> bool:
mid = self.get_middle_node(head)
reversed_head = self.get_reversed_ll(mid)
m = head
n = reversed_head
while n:
if n.val != m.val:
return False
m =
n =
return True
def get_middle_node(self, head):
s = f = head
while f and
s =
f =
return s
def get_reversed_ll(self, head):
d = ListNode(-1) = head
cur = = None
while cur:
nxt = = = cur
cur = nxt
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment