NUHMAN.com

🔍 Problem Statement

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

A palindrome is a word, number, phrase, or other sequence of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization).

Example 1:

go

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

Example 2:

go

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

🧠 Approach

To check if a singly linked list is a palindrome, we can use a two-pointer approach. Here’s the strategy:

1. Step 1: Find the middle of the linked list:

• Use the slow and fast pointers (Tortoise and Hare technique) to find the middle of the list. The fast pointer moves two steps at a time, and the slow pointer moves one step at a time. When the fast pointer reaches the end, the slow pointer will be at the middle.

1. Step 2: Reverse the second half of the list:

• After finding the middle, reverse the second half of the list starting from the slow pointer’s position.

1. Step 3: Compare the two halves:

• Compare the first half and the reversed second half of the list. If they are identical, then the list is a palindrome.

1. Step 4: Restore the list (optional):

• If necessary, restore the list by reversing the second half again, though it's not required in this problem.

✅ Go Implementation

go

package main

import "fmt"

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

// Function to check if the linked list is a palindrome
func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }

    // Step 1: Find the middle of the list using slow and fast pointers
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // Step 2: Reverse the second half of the list
    var prev *ListNode
    for slow != nil {
        nextTemp := slow.Next
        slow.Next = prev
        prev = slow
        slow = nextTemp
    }

    // Step 3: Compare the two halves
    left, right := head, prev
    while right != nil {
        if left.Val != right.Val {
            return false
        }
        left = left.Next
        right = right.Next
    }

    return true
}

// Helper function to create a linked list from an array of values
func createLinkedList(values []int) *ListNode {
    if len(values) == 0 {
        return nil
    }

    head := &ListNode{Val: values[0]}
    current := head
    for _, val := range values[1:] {
        current.Next = &ListNode{Val: val}
        current = current.Next
    }

    return head
}

// Test the isPalindrome function
func main() {
    // Test case 1: Palindrome list
    head1 := createLinkedList([]int{1, 2, 2, 1})
    fmt.Println(isPalindrome(head1))  // Output: true

    // Test case 2: Non-palindrome list
    head2 := createLinkedList([]int{1, 2})
    fmt.Println(isPalindrome(head2))  // Output: false
}

🧑‍💻 Explanation of the Code

1. isPalindrome function:

• Step 1: We use the slow and fast pointer technique to find the middle of the list. slow moves one step at a time, and fast moves two steps at a time.
• Step 2: After finding the middle of the list, we reverse the second half of the list. We keep track of the previous node (prev) while moving the slow pointer to reverse the list.
• Step 3: Finally, we compare the first half of the list with the reversed second half. If they match, the list is a palindrome; otherwise, it is not.

1. createLinkedList function:

• This helper function converts an array of integers into a linked list. It starts by creating the head node and then iterates through the array to build the rest of the list.

📦 Example Usage

go

func main() {
    // Test case 1: Palindrome list
    head1 := createLinkedList([]int{1, 2, 2, 1})
    fmt.Println(isPalindrome(head1))  // Output: true

    // Test case 2: Non-palindrome list
    head2 := createLinkedList([]int{1, 2})
    fmt.Println(isPalindrome(head2))  // Output: false
}

⏱️ Time & Space Complexity

• Time Complexity: O(n)
• The algorithm has three main parts: finding the middle, reversing the second half, and comparing the two halves. Each part processes each node at most once, so the time complexity is linear in the number of nodes, which is O(n).
• Space Complexity: O(1)
• We use only a few pointers to perform the operations (slow, fast, prev, left, and right), so the space complexity is constant.

This solution efficiently checks if a singly linked list is a palindrome with a time complexity of O(n) and space complexity of O(1).