0234 - Palindrome Linked List (Easy)

Problem Statement

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

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?

Approach 1: Fast & Slow Pointers

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // find the middle node
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        // handle odd case
        if(fast) slow = slow->next;
		// reverse the last half of the list
        ListNode *node = slow;
        ListNode *last = nullptr;
        ListNode *next = nullptr;
        while(node){
            next = node->next;
            node->next = last;
            last = node;
            node = next;
        }
		// compare each half of the list
        node = last;
        while(node){
            if (node->val == head->val) node = node->next, head = head->next;
            else return false;
        }
        return true;
    }
};

# 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

        # find middle value(slow)
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # reverse second portion
        prev = None # dummy
        while slow:
            tmp = slow.next
            slow.next = prev
            prev = slow
            slow = tmp

        # check if it's palindrome
        left, right = head, prev
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next

        return True

/**
 * 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) {
  let slow = head;
  let fast = head;
  // find middle value(slow)
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // reverse second portion
  let prev = null;
  while (slow) {
    let temp = slow.next;
    slow.next = prev;
    prev = slow;
    slow = temp;
  }
  // check if it's palindrome
  let left = head;
  let right = prev;
  while (right) {
    if (left.val != right.val) {
      return false;
    }
    left = left.next;
    right = right.next;
  }
  return true;
};

Approach 2: Convert it to String

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // convert it to a string
        string s;
        while (head != NULL) {
            s += head->val;
            head = head->next;
        }
        // test if a string is palindrome
        string t = s;
        reverse(t.begin(), t.end());
        return s == t;
    }
};

/**
 * 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) {
  let head_str = new String();
  // convert to string
  while (head) {
    head_str += head.val;
    head = head.next;
  }
  // return true if it's palindrome
  return head_str == head_str.split('').reverse().join('');
};

# 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:
        head_str = ''
        # convert to string
        while head:
            head_str += str(head.val)
            head = head.next
        # return true if it's palindrome
        return head_str == head_str[::-1]

Approach 3: Stack

Iterative approach using Stack

Push first half of the elements onto a stack.
Iterate through the linked list, using fast runner / slow runner technique.
At each step, push the data from the slow runner onto a stack
When the fast runner hits the end of the list, the slow runner will have reached the middle of the list.
By this point, the stack will have all the elements from the front of the linked list, but in reverse order Last, iterate through the rest of the slow runner node, and compare the node to the top of the stack.

Time Complexity: $O(n)$ , where $n$ - # of nodes in the list

Space complexity: $O(n)$

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // Stack
        Stack<Integer> stack = new Stack<>();
        // Fast & Slow runner iteration
        while (fast != null && fast.next != null) {
            stack.push(slow.val);
            fast = fast.next.next;
            slow = slow.next;
        }
        // If list has odd number of elements, Skip the middle element
        if (fast != null) {
            slow = slow.next;
        }
        while (slow != null) {
            int value = stack.pop().intValue();
            if (slow.val != value) {
                return false;
            }
            slow = slow.next;
        }
        return true;
    }
}

Approach 4: Follow up: O(n) time, O(1) space

Easy steps to solve the problem,

Find the middle node
Reverse a list from middle
Compare both halves
Re-reverse the list (optional here), and return true if either of halves are empty