Palindrome Linked List

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

Examples:

Input: LinkedList: 1->2->1->1->2->1
Output: true
Explanation: The given linked list is 1->2->1->1->2->1 , which is a palindrome and Hence, the output is true.

Input: LinkedList: 1->2->3->4
Output: false
Explanation: The given linked list is 1->2->3->4, which is not a palindrome and Hence, the output is false.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1) 
Note: You should not use the recursive stack space as well

Constraints:
1 <= number of nodes <= 10⁵
1 ≤ node->data ≤ 10³

Approach 01:

class Solution {
  public:
    // Function to check whether the list is palindrome.
    bool isPalindrome(Node* head) {
        Node* slowPointer = head;
        Node* fastPointer = head;
        Node* previousPointer = nullptr;
        
        // Finding the middle of the linked list using two-pointer technique
        while (fastPointer && fastPointer->next) {
            previousPointer = slowPointer;
            slowPointer = slowPointer->next;
            fastPointer = fastPointer->next->next;
        }
        
        // Detaching the first half of the list
        if (previousPointer)
            previousPointer->next = nullptr;
        
        previousPointer = nullptr;
        
        // Reversing the second half of the linked list
        while (slowPointer) {
            Node* nextNode = slowPointer->next;
            slowPointer->next = previousPointer;
            previousPointer = slowPointer;
            slowPointer = nextNode;
        }
        
        // Comparing both halves
        while (head) {
            if (head->data != previousPointer->data)
                return false;
        
            head = head->next;
            previousPointer = previousPointer->next;
        }
        
        return true;
    }
};

class Solution:
    def isPalindrome(self, head):
        slowPointer = head
        fastPointer = head
        previousPointer = None
    
        # Finding the middle of the linked list using two-pointer technique
        while fastPointer and fastPointer.next:
            previousPointer = slowPointer
            slowPointer = slowPointer.next
            fastPointer = fastPointer.next.next
    
        # Detaching the first half of the list
        if previousPointer:
            previousPointer.next = None
    
        previousPointer = None
    
        # Reversing the second half of the linked list
        while slowPointer:
            nextNode = slowPointer.next
            slowPointer.next = previousPointer
            previousPointer = slowPointer
            slowPointer = nextNode
    
        # Comparing both halves
        while head:
            if head.data != previousPointer.data:
                return False
    
            head = head.next
            previousPointer = previousPointer.next
    
        return True

Time Complexity

• Finding the middle of the linked list:

  We use the slow and fast pointer technique to find the middle of the list. In each iteration, the slow pointer moves one step, and the fast pointer moves two steps. This step takes \(O(n / 2)\) time, where \(n\) is the number of nodes in the linked list.

• Reversing the second half of the list:

  Once we find the middle, we reverse the second half of the linked list. This operation iterates over the second half, which takes \(O(n / 2)\) time.

• Comparing the two halves:

  After reversing the second half, we compare it with the first half. This comparison takes \(O(n / 2)\) time.

• Overall Time Complexity:

  The operations (finding the middle, reversing, and comparing) are all linear in terms of the size of the list. Therefore, the total time complexity is \(O(n)\), where \(n\) is the length of the linked list.

Space Complexity

• Reversing the second half:

  We reverse the second half of the list in place, so no extra space is used for storing nodes.

• Pointer Variables:

  We use a constant amount of extra space for the pointers (slowPointer, fastPointer, previousPointer, and nextNode). These are all single variables, so the space complexity is constant \(O(1)\).

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as we are not using any extra space except for the pointer variables.