Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# liyunrui/234. Palindrome Linked List.py

Created Mar 13, 2021
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
to join this conversation on GitHub. Already have an account? Sign in to comment