DSA Visualizations | Hello Interview

Palindrome Linked List

DESCRIPTION (credit Leetcode.com)

Given a reference of type ListNode which is the head of a singly linked list, write a function to determine if the linked list is a palindrome.


# Definition of a ListNode
class ListNode:
  def __init__(self, value=0, next=None):
    self.value = value
    self.next = next

A linked list is a palindrome if the values of the nodes are the same when read from left-to-right and right-to-left. An empty list is considered a palindrome.

EXAMPLES

Example 1:

Output: True left-to-right: 5 -> 4 -> 3 -> 4 -> 5 right-to-left: 5 -> 4 -> 3 -> 4 -> 5

Example 2:

Output: False left-to-right: 5 -> 4 -> 3 right-to-left: 3 -> 4 -> 5

We recommend taking some time to solve the problem on your own before reading the solutions below.

Solutions

To determine if a linked list is a palindrome, we need to compare the values of the nodes when read from left-to-right and right-to-left. But since our linked list is singly linked, we can only read its values from left-to-right.

One way around this problem is to convert the linked list to a list, which supports reading values from both directions.

1. Convert to List: Compare Reverse

If we convert the original linked list to a list, we can compare the list with its reverse to determine if it is a palindrome. If the list is a palindrome, the list and its reverse will be equal.


def isPalindrome(head):
  # convert linked list to list
  vals = []
  current_node = head
  while current_node:
    vals.append(current_node.val)
    current_node = current_node.next

  # compare list with its reverse
  return vals == vals[::-1]

palindrome linked list

0 / 7

Time Complexity: O(n) where n is the number of nodes in the linked list. We iterate through each node in the linked list once to convert it to a list and then compare the list with its reverse, both of which are O(n) operations.

Space Complexity: O(n) where n is the number of nodes in the linked list, because we store the values of each node in a list.

2. Convert to List: Two-Pointer Technique

Instead of comparing the entire list with its reverse, we can use the two-pointer technique to check if the values in the list are a palindrome.

Like the previous solution, we first traverse the linked list and store the value of each node in a list.

Then, we initialize two pointers, left and right, at the start and end of the list, respectively. We compare the values at the left and right pointers. If they are equal, we move them both towards the center of the list. If the values at the left and right pointers are not equal, the list is not a palindrome.


def isPalindrome(head):
  # convert linked list to list
  vals = []
  current = head
  while current:
    vals.append(current.val)
    current = current.next

  left, right = 0, len(vals) - 1
  while left < right:
    if vals[left] != vals[right]:
      return False
    left, right = left + 1, right - 1

  return True

palindrome linked list

0 / 10

Time Complexity: O(n) where n is the number of nodes in the linked list. We iterate through each node in the linked list once to convert it to a list and then compare the values at the left and right pointers, which is also an O(n) operation. This is a slightly more time efficient solution than the previous one because we can stop as soon as we find a pair of values that are not equal during the palindrome check.

Space Complexity: O(n) where n is the number of nodes in the linked list. Like the previous solution, we store the values of each node in a list. This is also a slightly more space efficient solution than the previous one because we don't have to store the entire reverse of the list to compare it with the original.

3. Optimal Solution: Reverse Second Half

In the two-pointer above approach, we compared the first half of the list with the second half of the list, in reverse.

So if we first modify our linked list by reversing the direction of the nodes in the second half of the list, we can solve this problem without having to first convert the linked list to a list. This is the optimal solution, with a time complexity of O(n) and space complexity of O(1).

Step 1: Find the Middle of the Linked List

This step can be done using fast and slow pointers, which involves initializing two pointers, fast and slow, at the head of the linked list, and then iterating until fast reaches the end of the list. At each iteration, slow moves one node forward and fast moves two nodes forward. When fast reaches the tail node of the list, slow will point to the middle node in the list.


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

initialize pointers

0 / 2

When there are an even number of nodes, fast will equal to None after moving past the tail node, and slow will be the first node of the second half of the list. In the case below, there are 4 nodes, so slow will point to the 3rd node.


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

initialize pointers

0 / 2

Step 2: Reverse second half of list

At this point, slow points to the middle node in the list. Next, we want to reverse the direction of the pointers of each node starting from slow to the tail of the list.

Reversing the nodes in a linked list is a common problem that can be solved by iterating over each node that needs to be reversed. The key idea is to maintain three pointers, prev, curr, and next_, where prev points to the previous node, curr points to the node with the pointer we want to reverse, and next_ points to the next node in the iteration.

At each iteration, we:

save the next node in the iteration by setting next_ = curr.next
reverse the pointer by setting curr.next = prev
move pointers for the next iteration by set curr = next_ and prev = curr


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

find middle node

0 / 10

You need the next_pointer to store the next node in the iteration before overwriting the value of curr.next with prev. If you don't store the next node in the iteration, you will lose the reference to the rest of the linked list.

Step 3: Check for Palindrome

With the nodes reversed, we can now use two pointers to compare the values of the nodes in the first half of the list with the reversed second half of the list.

At this point, prev points to the head of the reversed second half of the list. We can set a pointer left equal to the head of the original list and right equal to prev.

We then iterate through the list, comparing the values at left and right. If the values are not equal, the list is not a palindrome. If they are equal, we move left and right towards the center of the list, until they meet at the same node, at which point we return True because our list is a palindrome.


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

curr = next_, prev = curr

0 / 5

Detecting the list is not a palindrome:


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

curr = next_, prev = curr

0 / 3

Returning false because 4 != 3

To recap:

Find the middle of the linked list using the fast and slow pointers technique.
Reverse the direction of the nodes in the second half of the linked list.
Use two-pointers to check for a palindrome by comparing the values of the nodes in the first half of the list with the reversed second half of the list.

Code

To construct the linked list that is used in the animation below, provide a list of integers nodes. Each integer in nodes is used as the value of a node in the linked list, and the order of the integers in the list will be the order of the nodes in the linked list.

For example, if nodes = [1, 2, 3], the linked list will be 1 -> 2 -> 3.


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

palindrome linked list

0 / 18

Edge Cases

Empty List

When the linked list is empty, all of the pointers will be None, and the function returns True immediately because an empty list is a palindrome.


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

palindrome linked list

0 / 4

nodes = []

Single Node

When the linked list has a single node:

fast.next is None, so the first while loop to find the middle node doesn't execute.
Reversing the second half of the list has no effect because there is only one node.
The palindrome check returns True because a single node is a palindrome.


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

palindrome linked list

0 / 8

nodes = [5]

Two Nodes (Palindrome)

When the linked list has two nodes:

The first while loop sets the slow pointer to the second node.
Reversing the second half of the list has no effect slow.next is None already.
The palindrome check compares the values of the two nodes and returns True if they are equal.


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

palindrome linked list

0 / 9

nodes = [2, 2]

Two Nodes (Not Palindrome)


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

palindrome linked list

0 / 8

nodes = [2, 3]

Complexity Analysis

Time Complexity: O(n) where n is the number of nodes in the linked list. We iterate through the linked list three times: once to find the middle node, once to reverse the second half of the list, and once to check for palindrome. All of these operations are O(n).

Space Complexity: O(1). The solution doesn't allocate any additional space other than a few pointers. Since the number of pointers stays fixed regardless of the number of nodes in the linked list, the space complexity is O(1).

Next: Remove Nth Node From End of List

Your account is free and you can post anonymously if you choose.

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Linked List Cycle

Remove Nth Node From End of List

Palindrome Linked List

DESCRIPTION (credit Leetcode.com)

Given a reference of type ListNode which is the head of a singly linked list, write a function to determine if the linked list is a palindrome.


# Definition of a ListNode
class ListNode:
  def __init__(self, value=0, next=None):
    self.value = value
    self.next = next

A linked list is a palindrome if the values of the nodes are the same when read from left-to-right and right-to-left. An empty list is considered a palindrome.

EXAMPLES

Example 1:

Output: True left-to-right: 5 -> 4 -> 3 -> 4 -> 5 right-to-left: 5 -> 4 -> 3 -> 4 -> 5

Example 2:

Output: False left-to-right: 5 -> 4 -> 3 right-to-left: 3 -> 4 -> 5

We recommend taking some time to solve the problem on your own before reading the solutions below.

Solutions

One way around this problem is to convert the linked list to a list, which supports reading values from both directions.

1. Convert to List: Compare Reverse

If we convert the original linked list to a list, we can compare the list with its reverse to determine if it is a palindrome. If the list is a palindrome, the list and its reverse will be equal.


def isPalindrome(head):
  # convert linked list to list
  vals = []
  current_node = head
  while current_node:
    vals.append(current_node.val)
    current_node = current_node.next

  # compare list with its reverse
  return vals == vals[::-1]

palindrome linked list

0 / 7

Space Complexity: O(n) where n is the number of nodes in the linked list, because we store the values of each node in a list.

2. Convert to List: Two-Pointer Technique

Instead of comparing the entire list with its reverse, we can use the two-pointer technique to check if the values in the list are a palindrome.

Like the previous solution, we first traverse the linked list and store the value of each node in a list.


def isPalindrome(head):
  # convert linked list to list
  vals = []
  current = head
  while current:
    vals.append(current.val)
    current = current.next

  left, right = 0, len(vals) - 1
  while left < right:
    if vals[left] != vals[right]:
      return False
    left, right = left + 1, right - 1

  return True

palindrome linked list

0 / 10

3. Optimal Solution: Reverse Second Half

In the two-pointer above approach, we compared the first half of the list with the second half of the list, in reverse.

Step 1: Find the Middle of the Linked List


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

initialize pointers

0 / 2


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

initialize pointers

0 / 2

Step 2: Reverse second half of list

At this point, slow points to the middle node in the list. Next, we want to reverse the direction of the pointers of each node starting from slow to the tail of the list.

At each iteration, we:

save the next node in the iteration by setting next_ = curr.next
reverse the pointer by setting curr.next = prev
move pointers for the next iteration by set curr = next_ and prev = curr


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

find middle node

0 / 10

Step 3: Check for Palindrome

With the nodes reversed, we can now use two pointers to compare the values of the nodes in the first half of the list with the reversed second half of the list.

At this point, prev points to the head of the reversed second half of the list. We can set a pointer left equal to the head of the original list and right equal to prev.


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

curr = next_, prev = curr

0 / 5

Detecting the list is not a palindrome:


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

curr = next_, prev = curr

0 / 3

Returning false because 4 != 3

To recap:

Find the middle of the linked list using the fast and slow pointers technique.
Reverse the direction of the nodes in the second half of the linked list.
Use two-pointers to check for a palindrome by comparing the values of the nodes in the first half of the list with the reversed second half of the list.

Code

For example, if nodes = [1, 2, 3], the linked list will be 1 -> 2 -> 3.


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

palindrome linked list

0 / 18

Edge Cases

Empty List

When the linked list is empty, all of the pointers will be None, and the function returns True immediately because an empty list is a palindrome.


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

palindrome linked list

0 / 4

nodes = []

Single Node

When the linked list has a single node:

fast.next is None, so the first while loop to find the middle node doesn't execute.
Reversing the second half of the list has no effect because there is only one node.
The palindrome check returns True because a single node is a palindrome.


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

palindrome linked list

0 / 8

nodes = [5]

Two Nodes (Palindrome)

When the linked list has two nodes:

The first while loop sets the slow pointer to the second node.
Reversing the second half of the list has no effect slow.next is None already.
The palindrome check compares the values of the two nodes and returns True if they are equal.


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

palindrome linked list

0 / 9

nodes = [2, 2]

Two Nodes (Not Palindrome)


def is_palindrome(head):
  # find middle node of the list
  slow = fast = head
  while fast and fast.next:
    fast = fast.next.next
    slow = slow.next

  # reverse second half of the list
  curr, prev = slow, None
  while curr:
    next_ = curr.next # save next node
    curr.next = prev # reverse pointer
    prev = curr # move pointers
    curr = next_

  # Check palindrome
  left, right = head, prev
  while right:
    if left.val != right.val:
      return False
    left = left.next
    right = right.next
  return True

palindrome linked list

0 / 8

nodes = [2, 3]

Complexity Analysis

Next: Remove Nth Node From End of List

Your account is free and you can post anonymously if you choose.

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103