Palindrome Linked List

---

Palindrome Linked List: 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

---

Example 3:

Input: head = []
Output: []

---

Constraints:

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

---

Try this Problem on your own or check similar problems:

1. Palindrome Number
2. Valid Palindrome

Solution:

Java

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next == null) return true;
        ListNode prev = null, slow = head, fast = head;
        while(fast != null && fast.next != null){
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        ListNode iter1 = head, iter2 = reverseList(slow);
        while(iter1 != null && iter2 != null){
            if(iter1.val != iter2.val) return false;
            iter1 = iter1.next;
            iter2 = iter2.next;
        }
        return true;
    }

    private ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode prev = null, next = head, curr = prev;

        while(next != null){
            curr = next;
            next = next.next;
            curr.next = prev;
            prev = curr;
        }

        return prev;
    }
}

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
  if (head.next === null) return true;
  let prev = null;
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }
  prev.next = null;
  let iter1 = head;
  let iter2 = reverseList(slow);
  while (iter1 !== null && iter2 !== null) {
    if (iter1.val !== iter2.val) return false;
    iter1 = iter1.next;
    iter2 = iter2.next;
  }
  return true;
};

function reverseList(head) {
  if (head === null || head.next === null) return head;

  let prev = null;
  let next = head;
  let curr = prev;

  while (next !== null) {
    curr = next;
    next = next.next;
    curr.next = prev;
    prev = curr;
  }

  return prev;
}

Python

# 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:
      if head.next is None:
          return True
      prev = None
      slow = head
      fast = head
      while fast is not None and fast.next is not None:
          prev = slow
          slow = slow.next
          fast = fast.next.next
      prev.next = None
      iter1 = head
      iter2 = self.reverseList(slow)
      while iter1 is not None and iter2 is not None:
          if iter1.val != iter2.val:
              return False
          iter1 = iter1.next
          iter2 = iter2.next
      return True

    def reverseList(self, head):
      if head is None or head.next is None:
          return head

      prev = None
      next = head
      curr = prev

      while next is not None:
          curr = next
          next = next.next
          curr.next = prev
          prev = curr

      return prev

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->next == nullptr) return true;
        ListNode* prev = nullptr;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        prev->next = nullptr;
        ListNode* iter1 = head;
        ListNode* iter2 = reverseList(slow);
        while (iter1 != nullptr && iter2 != nullptr) {
            if (iter1->val != iter2->val) return false;
            iter1 = iter1->next;
            iter2 = iter2->next;
        }
        return true;
    }

private:
  ListNode* reverseList(ListNode* head) {
      if (head == nullptr || head->next == nullptr) return head;

      ListNode* prev = nullptr;
      ListNode* next = head;
      ListNode* curr = prev;

      while (next != nullptr) {
          curr = next;
          next = next->next;
          curr->next = prev;
          prev = curr;
      }

      return prev;
  }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

It's obvious that we could iterate the first half of linked list and put it in a stack for example and then pop the elements and check if the value is the same when traversing the second half of the list. We get linear space complexity, but can we improve on it? We use the reverse linked list implementation from Reverse Linked List to reverse the second half of the linked list and then move simultaneously two pointers checking if the values at each are equal. One pointer (or iterator) starts from the head of the linked list, while the header points to the new head of the reversed list. If we have a match between every pair of the two halves we return true since the list is a palindrome. How do we find the middle of the list? Well we can use the slow and fast pointer method as shown in Middle of Linked List. For the sake of competition let's do the recursive solution too:

Java

class Solution {
    private ListNode curr;
    public boolean isPalindrome(ListNode head) {
        curr = head;
        return helper(head);
    }
    private boolean helper(ListNode head) {
        if (head == null) return true;
        boolean isPalindrome = helper(head.next) & (curr.val == head.val);
        curr = curr.next;
        return isPalindrome;
    }
}

JavaScript

var isPalindrome = function (head) {
  let curr = { node: head };
  return helper(head, curr);
};

function helper(head, curr) {
  if (head === null) return true;
  let isPalindrome = helper(head.next, curr) && curr.node.val === head.val;
  curr.node = curr.node.next;
  return isPalindrome;
}

Python

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        curr = [head]
        return self.helper(head, curr)

    def helper(self, head, curr):
        if head is None:
            return True
        isPalindrome = self.helper(head.next, curr) and (curr[0].val == head.val)
        curr[0] = curr[0].next
        return isPalindrome

C++

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        curr = head;
        return helper(head);
    }

private:
    ListNode* curr;
    bool helper(ListNode* head) {
        if (head == nullptr) return true;
        bool isPalindrome = helper(head->next) && (curr->val == head->val);
        curr = curr->next;
        return isPalindrome;
    }
};

Note that the space complexity with recursion is the same as iterative one using stack O(n).