Palindrome Linked List easy

Problem Statement

Given the head of a singly linked list, return true if it is a palindrome, or false otherwise.

Example 1:

Input: head = [1,2,2,1] Output: true

Example 2:

Input: head = [1,2] Output: false

Steps

1. Find the middle of the linked list: We use the slow and fast pointer technique. The slow pointer moves one step at a time, and the fast pointer moves two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle.

2. Reverse the second half of the linked list: We reverse the linked list starting from the middle node.

3. Compare the first half and the reversed second half: We compare the nodes of the first half with the nodes of the reversed second half. If they are all the same, the linked list is a palindrome. Otherwise, it's not.

Explanation

The algorithm leverages the concept of slow and fast pointers to efficiently find the middle of the linked list in O(N) time. Reversing the second half is also an O(N) operation. Finally, comparing the two halves takes O(N/2) which simplifies to O(N). Therefore, the overall time complexity is O(N). Space complexity is O(1) because we're modifying the list in place rather than creating a new data structure to store the reversed second half (except for a few temporary variables).

Code

using System;
using System.Collections.Generic;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public bool IsPalindrome(ListNode head) {
        // Handle empty or single-node lists
        if (head == null || head.next == null) return true;

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

        // Reverse the second half of the linked list
        ListNode prev = null;
        ListNode curr = slow;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

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

        return true;
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. This is because we traverse the list multiple times (finding the middle, reversing the second half, and comparing the halves).
• Space Complexity: O(1). The algorithm uses only a constant amount of extra space.