[Top Interview Questions] 234. Palindrome Linked List

Solution)

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        fast, slow = head, head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        prev = None
        while slow:
            temp = slow.next
            slow.next = prev
            prev = slow
            slow = temp
        
        left, right = head, prev
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        
        return True

 

Time Complexity: O(n)

Space Complexity: O(1)

 

Reference: NeetCode

Problem: LeetCode

Explanation)

I was able to solve this problem using O(n) of space complexity, but I couldn't figure out how to solve this using O(1) of space complexity.

 

According to NeetCode's solution, the three big steps were

1) Finding the middle node of the linked list

2) Reversing the second half of the linked list

3) Checking if the first half and the second half are identical

Finding the middle node)

First we're going to use torioise and hare technique to find the middle node.

Once the hare pointer reaches null (or hare.next reaches null), that means the tortoise node must have reached the middle node.

tortoise and hare in even/odd linked list

Using this method, we can find the middle node of the linked list.

 

def isPalindrome(self, head: Optional[ListNode]) -> bool:
        fast, slow = head, head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

Reversing the second half)

As we have found a node where the second half starts, we can then reverse the second half so that we can compare the first and the scond halves to see if they are identical.

 

To reverse a linked list, you need three variables prev, slow, temp.

Let's assume there is a linked list of 3 - 2 - 1

 

prev variable holds nodes that should appear before a current node.

For example, if the current node is 2, prev would be 3.

Then we would make the current node's next to be prev, which makes that current node 2 - 3.

 

slow variable represents the current node. So we would need to update slow to its next node after we attach prev to slow.

In this case, slow variable will become node 1.

 

temp variable is slow's next node. We need to save that next node to a temporary variable because we not only need to update slow's next node to prev but also need the information of slow's original next node.

 

Reversing a linked list

 

def isPalindrome(self, head: Optional[ListNode]) -> bool:
        fast, slow = head, head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        prev = None
        while slow:
            temp = slow.next
            slow.next = prev
            prev = slow
            slow = temp

Compare first/second halves of the linked list)

Set left to the head of the list and set right to the start of the second half.

Since the length of head to null is longer than prev to null, we are going to compare them while right is not null.

 

If we find left and right don't have the same value, we'll return False.

If the iteration through the while loop is complete, the linked list is a palindrome so we return True.

 

def isPalindrome(self, head: Optional[ListNode]) -> bool:
        fast, slow = head, head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        prev = None
        while slow:
            temp = slow.next
            slow.next = prev
            prev = slow
            slow = temp
        
        left, right = head, prev
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        
        return True

 

 

For LeetCode problems, I will be explaining solutions in English. I'm considering solving 백준 after this Top Interview Questions and will be explaining those problems in Korean. I never thought about reversing a linked list in place. Might be pretty useful for other problems. 

 

Thank you for reading my post and please let me know if you have any quesitons :)