Solutions

1. Extra Array

O(n) time | O(n) space

Intuition

We can first create an array with all the linked list values.

Then we compare corresponding values with one loop and two indexes on both ends of the array moving towards each other.

Algorithm

Create an empty array.
Traverse through the linked list from the head to the end, adding the value of every node to the array.
When the loop finishes, set the left index to the first element and the right index to the last element of the array.
Iterate through the loop while left is less than right, moving left one step to the right and right one step to the left after each iteration.
Return false if the values on left and right differ at any iteration, and true if the loop finishes.

1 → 2 → 3 → 2 → 1

01234

left right

take 1

1 / 9

Code

# Definitions:
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def isPalindrome(head: ListNode) -> bool:
    values = []
    node = head
    while node:
        values.append(node.val)
        node = node.next
    left, right = 0, len(values) - 1
    while left < right:
        if values[left] != values[right]:
            return False
        left += 1
        right -= 1
    return True

// Definitions:
// function ListNode(val, next) {
//     this.val = val === undefined ? 0 : val
//     this.next = next === undefined ? null : next
// }

/**
 * @param {ListNode} head
 * @returns {boolean}
 */
var isPalindrome = function (head) {
  const values = []
  let node = head
  while (node) {
    values.push(node.val)
    node = node.next
  }
  let left = 0
  let right = values.length - 1
  while (left < right) {
    if (values[left] !== values[right]) return false
    left++
    right--
  }
  return true
}

// Definitions:
// class ListNode {
//     int val;
//     ListNode next;
//
//     ListNode() {}
//
//     ListNode(int val) {
//         this.val = val;
//     }
//
//     ListNode(int val, ListNode next) {
//         this.val = val;
//         this.next = next;
//     }
// }

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) {
            values.add(node.val);
        }
        int left = 0;
        int right = values.size() - 1;
        while (left < right) {
            if (!values.get(left).equals(values.get(right))) return false;
            left++;
            right--;
        }
        return true;
    }
}

2. Fast and Slow Pointers

O(n) time | O(1) space

Intuition

We can find the middle node with a slow and a fast pointer, where the fast one moves two nodes for every one node of the slow one.

Then we can reverse the second part of the list from the middle and traverse both parts together, comparing the values at each iteration.

Algorithm

Set both the slow and the fast pointer to the head.
Traverse through the list moving the slow pointer one node and the fast pointer two nodes.
Reverse the list from the slow pointer when the loop finishes.
Traverse from the original head and the reversed head together.
Return false if the values differ at any iteration, and true if the loop finishes.

1 → 2 → 3 → 2 → 1 slowfastleftright

move slow 1 step, fast 2 steps

1 / 8

Code

# Definitions:
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def isPalindrome(head: ListNode) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    previous = None
    current = slow
    while current:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node

    left, right = head, previous
    while right:
        if left.val != right.val:
            return False
        left, right = left.next, right.next

    return True

// Definitions:
// function ListNode(val, next) {
//     this.val = val === undefined ? 0 : val
//     this.next = next === undefined ? null : next
// }

/**
 * @param {ListNode} head
 * @returns {boolean}
 */
var isPalindrome = function (head) {
  let slow = head
  let fast = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
  }

  let previous = null
  let current = slow
  while (current) {
    const nextNode = current.next
    current.next = previous
    previous = current
    current = nextNode
  }

  let left = head
  let right = previous
  while (right) {
    if (left.val !== right.val) return false
    left = left.next
    right = right.next
  }

  return true
}

// Definitions:
// 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 slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode previous = null;
        ListNode current = slow;
        while (current != null) {
            ListNode nextNode = current.next;
            current.next = previous;
            previous = current;
            current = nextNode;
        }

        ListNode left = head;
        ListNode right = previous;
        while (right != null) {
            if (left.val != right.val) return false;
            left = left.next;
            right = right.next;
        }

        return true;
    }
}