LeetCode #234 Palindrome Linked List

Posted on | Post modified | In , , , , , , , , ,

Problem

Given a singly linked list, determine if it is a palindrome.

Examples

1
2
Input: 1->2
Output: false
1
2
Input: 1->2->2->1
Output: true

Solution1

Method: Brute Force

Time Complexity: O(n)

Space Complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return True
        
        array = []
        while head:
            array.append(head.val)
            head = head.next
            
        return array == array[::-1]

Solution2

Method:

Time Complexity: O(n)

Space Complexity: O(1)

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
39
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return True
        
        low = fast = head
        
        # find the mid node
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        # reverse the second half
        node = None
        while slow:
            nxt = slow.next
            slow.next = node
            node = slow
            slow = nxt
        
        # compare the first and second half nodes
        while node: # while node and head:
            if node.val != head.val:
                return False
            
            node = node.next
            head = head.next
        
        return True

or-time-O(1)-space)

1
2
3
4
5
6
7
8
9
10
11
12
def isPalindrome(self, head):
    rev = None
    slow = fast = head
    while fast and fast.next:
        fast = fast.next.next
        rev, rev.next, slow = slow, rev, slow.next
    if fast:
        slow = slow.next
    while rev and rev.val == slow.val:
        slow = slow.next
        rev = rev.next
    return not rev