Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-LL
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
"""
d->1->2->2->1
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:
nums.append(cur.val)
cur = cur.next
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 = m.next
n = n.next
return True
def get_middle_node(self, head):
s = f = head
while f and f.next:
s = s.next
f = f.next.next
return s
def get_reversed_ll(self, head):
d = ListNode(-1)
d.next = head
cur = head.next
head.next = None
while cur:
nxt = cur.next
cur.next = d.next
d.next = cur
cur = nxt
return d.next
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment