234. Palindrome Linked List

Problem Link

Description

---

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

 

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

 

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

 

Follow up: Could you do it in O(n) time and O(1) space?

Solution

---

Python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
 
        # 1) move slow pointer to the middle of the linked list
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        def reverseLL(curr):
            prev = None
 
            while curr:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt
            
            return prev
 
        # 2) reverse the second half of the linked list
        rhead = reverseLL(slow)
 
        # 3) compare the first half and the reversed second half
        while rhead:
            if head.val != rhead.val:
                return False
            
            head = head.next
            rhead = rhead.next
        
        return True

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return true;
        
        ListNode *slow = head, *fast = head;
        
        while (fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        
        slow->next = reverseLL(slow->next);
        slow = slow->next;
        
        while (slow){
            if (head->val != slow->val) return false;
            
            head = head->next;
            slow = slow->next;
        }
        
        return true;
        
    }
    
    ListNode* reverseLL(ListNode *node){
        ListNode *res = NULL;
        
        while (node){
            ListNode *next = node->next;
            node->next = res;
            res = node;
            node = next;
        }
        
        return res;
    }
};