Palindrome Linked List

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

# 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)O(n) time and O(1)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