Palindrome Linked List

Math

# Definition for Singly-Linked List

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

1
2
3
4

# Solution

All solutions below take linear time.

# Linear Space

# Two Pointers

def isPalindrome(self, head: ListNode) -> bool:
vals = []
curr = head
while curr:
vals.append(curr.val)
curr = curr.next

return vals == vals[::-1]

1
2
3
4
5
6
7
8

# Recursion

def isPalindrome(self, head: ListNode) -> bool:
self.front = head

def check(curr=head):
if curr:
if not check(curr.next):
return False
if curr.val != self.front.val:
return False
self.front = self.front.next
return True

return check()

1
2
3
4
5
6
7
8
9
10
11
12
13

# Follow Up

Could you do it in $O(n)$ time and $O(1)$ space?

# Constant Space

# Fast and Slow Pointers

Need to reverse then 2nd half to save space. As good practice, should reverse it back before return.

def isPalindrome(self, head: ListNode) -> bool:
if not head:
return True

# find tail node of the 1st half
fst_half_end = self.end_of_fst_half(head)
# reverse the 2nd half
snd_half_start = self.reverse_list(fst_half_end.next)

# check if palindrome
res = True
fst, snd = head, snd_half_start
while res and snd:
if fst.val != snd.val:
res = False
fst, snd = fst.next, snd.next

# restore linked list
fst_half_end.next = self.reverse_list(snd_half_start)
return res

def end_of_fst_half(self, head):
fast = head
slow = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
return slow

def reverse_list(self, head):
prev = None
curr = head
while curr:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
return prev

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38