Posts Palindrome Linked List (geeksforgeeks - SDE Sheet)
Post
Cancel

Palindrome Linked List (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given a singly linked list of integers. The task is to check if the given linked list is palindrome or not.

geeksforgeeks

SOLUTION

To solve this, we can reverse the second half of the linked list and then compare it with the first half. First, we use two pointers (slow and fast) to find the middle of the list. After reaching the middle, we reverse the second half of the list. Next, we compare the nodes from the first half with the nodes from the reversed second half. If all the nodes match, the list is a palindrome. Finally, we restore the original order of the list by reversing the second half back to its original form.

One important thing to handle is when the list is of odd length. After reversing, one of the lists will have one extra node. In my solution, I have kept it in the second list. So, after reversing the second list, that node will go to the end of the list. One way to handle it is by counting the number of nodes in list1. Then, we can just compare those many nodes in the two lists, ignoring the last node automatically.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {

    boolean isPalindrome(Node head) {

        // If the list is empty or has only one node, it's a palindrome
        if(head == null || head.next == null)
            return true;

        // Initialize slow and fast pointers for finding the middle of the list
        Node slow = head;
        Node fast = head.next;

        // number of nodes in list1
        int count = 1;

        // Move fast pointer by 2 steps and slow pointer by 1 step
        // Fast will reach the end twice as quickly, while slow will reach the middle
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
            count++;
        }

        // Reverse the second half of the linked list starting from the node after 'slow'
        slow.next = reverseLinkedList(slow.next);

        // Pointers to traverse the first and second half for comparison
        Node p1 = head;
        Node p2 = slow.next;

        // Compare the first half and reversed second half node by node
        for(int k = 0; k < count; k++){

            // If corresponding data in both halves don't match, it's not a palindrome
            if(p1.data != p2.data)
                return false;

            // Move both pointers forward
            p1 = p1.next;
            p2 = p2.next;

        }

        // Restore the modified linked list by reversing the second half back to original
        slow.next = reverseLinkedList(slow.next);

        // If no mismatches found, it's a palindrome
        return true;
    }

    // Helper function to reverse the linked list
    Node reverseLinkedList(Node head){

        Node h1 = head;
        Node h2 = null;

        while(h1 != null){
            Node t = h1;
            h1 = h1.next;
            t.next = h2;
            h2 = t;
        }

        return h2;
    }
}
This post is licensed under CC BY 4.0 by the author.