Check if a Singly Linked List is Palindrome or not

Given a singly linked list, the task is to check if the linked list is a palindrome. A linked list is a palindrome if it reads the same forward and backward.

Input-Output Examples

Example 1:

  • Input: 1 -> 2 -> 2 -> 1 -> NULL
  • Output: True

Example 2:

  • Input: 1 -> 2 -> 3 -> 2 -> 1 -> NULL
  • Output: True

Example 3:

  • Input: 1 -> 2 -> 3 -> 4 -> NULL
  • Output: False

Approach:

To check if a linked list is a palindrome, we can use the following approach:

  1. Find the Middle of the List:
    • Use the slow and fast pointer technique to find the middle of the list.
  2. Reverse the Second Half:
    • Reverse the second half of the linked list.
  3. Compare Both Halves:
    • Compare the first half with the reversed second half.
  4. Restore the List (Optional):
    • Restore the original list structure by reversing the second half back.

C++ Program to Check if the linked list is palindrome or not

cpp
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Function to reverse the linked list
ListNode* reverseList(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* current = head;
    ListNode* next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

// Function to check if the linked list is a palindrome
bool isPalindrome(ListNode* head) {
    if (head == NULL || head->next == NULL) return true;
    
    // Find the middle of the linked list
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // Reverse the second half of the list
    ListNode* secondHalf = reverseList(slow->next);
    ListNode* firstHalf = head;

    // Compare the first half with the reversed second half
    while (secondHalf != NULL) {
        if (firstHalf->val != secondHalf->val) {
            return false;
        }
        firstHalf = firstHalf->next;
        secondHalf = secondHalf->next;
    }

    return true;
}

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Creating a linked list: 1 -> 2 -> 2 -> 1 -> NULL
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(1);

    // Check if the linked list is a palindrome
    if (isPalindrome(head)) {
        cout << "The linked list is a palindrome." << endl;
    } else {
        cout << "The linked list is not a palindrome." << endl;
    }

    return 0;
}

Java Program to Check if the linked list is palindrome or not

java
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Main {
    // Function to reverse the linked list
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }

    // Function to check if the linked list is a palindrome
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        // Find the middle of the linked list
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Reverse the second half of the list
        ListNode secondHalf = reverseList(slow.next);
        ListNode firstHalf = head;

        // Compare the first half with the reversed second half
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                return false;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }

        return true;
    }

    // Helper function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        // Creating a linked list: 1 -> 2 -> 2 -> 1 -> NULL
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);

        // Check if the linked list is a palindrome
        if (isPalindrome(head)) {
            System.out.println("The linked list is a palindrome.");
        } else {
            System.out.println("The linked list is not a palindrome.");
        }
    }
}

Python Program to Check if the linked list is palindrome or not

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# Function to reverse the linked list
def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

# Function to check if the linked list is a palindrome
def is_palindrome(head):
    if not head or not head.next:
        return True

    # Find the middle of the linked list
    slow = head
    fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse the second half of the list
    second_half = reverse_list(slow.next)
    first_half = head

    # Compare the first half with the reversed second half
    while second_half:
        if first_half.val != second_half.val:
            return False
        first_half = first_half.next
        second_half = second_half.next

    return True

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating a linked list: 1 -> 2 -> 2 -> 1 -> NULL
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(2)
head.next.next.next = ListNode(1)

# Check if the linked list is a palindrome
if is_palindrome(head):
    print("The linked list is a palindrome.")
else:
    print("The linked list is not a palindrome.")

DSA

1176

481

Related Articles