Palindrome Linked List

Time: O(n)

Space: O(1)

Intuition

Find the midpoint (slow/fast pointers), reverse the second half, compare with the first half, then optionally restore. O(n) time, O(1) space.

Algorithm

1Find mid: slow/fast pointers.
2Reverse the second half starting from mid.next.
3Compare first half (head) with reversed second half. Track if palindrome.
4Optionally restore the second half.

Example Walkthrough

Input: 1â†’2â†’2â†’1

1.Mid = node(2) at index 1. Reverse second half: 1â†’2.
2.Compare: 1==1, 2==2. Palindrome!

Output: true

Common Pitfalls

•Restore the list after comparison if the problem requires (most GFG solutions need immutable input).

Palindrome Linked List.java

Java

// Approach: Find middle, reverse second half, compare with first half, restore list.
// Time: O(n) Space: O(1)
class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class Solution {
    // Function to check whether the list is palindrome.
    boolean isPalindrome(Node head) {
        if (head == null || head.next == null) // edge case
            return true;

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

        Node mid = slow;

        // Reverse the half of linked list from mid.next
        Node curr = mid.next;
        mid.next = null;
        Node prev = null;
        Node front = curr.next;

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

        // Check that two halves are equal or not
        slow = head;
        while (slow != null && curr != null) {
            if (slow.data != curr.data)
                return false;
            slow = slow.next;
            curr = curr.next;
        }
        return true;
    }
}

// Version 2
class Solution1 {
    public boolean isPalindrome(Node head) {
        if (head.next == null)
            return true;

        Node fast = head, slow = head, prev = null, nextStart = null;
        while (fast != null) {
            fast = fast.next;
            if (fast == null) { // edge case -> odd no of items, dont consider middle
                nextStart = slow.next;
                slow = prev;
                break;
            }
            if (fast.next == null)
                break;
            fast = fast.next;

            // reverse previous pointers of slow
            Node temp = slow;
            slow = slow.next;
            temp.next = prev;
            prev = temp;
        }

        if (slow != null && nextStart == null) {
            nextStart = slow.next;
            slow.next = prev;
        }

        // simple check for palindrome
        while (nextStart != null && slow != null) {
            if (nextStart.data != slow.data)
                return false;
            nextStart = nextStart.next;
            slow = slow.next;
        }

        return slow == null && nextStart == null;
    }
}

Was this solution helpful?