Check if a Linked List is a Palindrome in Go

Program Code

package main

import "fmt"

// ListNode defines a node in a singly linked list
type ListNode struct {
    Val  int
    Next *ListNode
}

// isPalindrome checks if the linked list is a palindrome
func isPalindrome(head *ListNode) bool {
    // Find the middle of the linked list
    slow, fast := head, head
    var prev *ListNode
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        next := slow.Next
        slow.Next = prev
        prev = slow
        slow = next
    }

    // For odd length lists, skip the middle element
    secondHalf := slow
    if fast != nil {
        secondHalf = slow.Next
    }

    // Restore the first half of the list
    firstHalf := prev
    slow = firstHalf
    for slow != nil {
        next := slow.Next
        slow.Next = prev
        prev = slow
        slow = next
    }

    // Compare both halves
    firstHalf = prev
    for firstHalf != nil && secondHalf != nil {
        if firstHalf.Val != secondHalf.Val {
            return false
        }
        firstHalf = firstHalf.Next
        secondHalf = secondHalf.Next
    }

    return true
}

// Helper function to print the linked list
func printList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val, " ")
        head = head.Next
    }
    fmt.Println()
}

// Main function to test the isPalindrome function
func main() {
    // Create a linked list: 1 -> 2 -> 3 -> 2 -> 1
    head := &ListNode{1, &ListNode{2, &ListNode{3, &ListNode{2, &ListNode{1, nil}}}}}

    fmt.Print("List: ")
    printList(head)

    // Check if the linked list is a palindrome
    if isPalindrome(head) {
        fmt.Println("The linked list is a palindrome.")
    } else {
        fmt.Println("The linked list is not a palindrome.")
    }
}
    

Explanation

The Go program is designed to check if a singly linked list is a palindrome. Here is a detailed explanation of the program structure:

1. ListNode Definition

The ListNode struct defines a node in a singly linked list, which contains a value (Val) and a pointer to the next node (Next).

2. isPalindrome Function

The isPalindrome function determines if the linked list is a palindrome:

• Uses two pointers, slow and fast, to find the middle of the linked list. The fast pointer moves twice as fast as the slow pointer.
• Reverses the first half of the list while finding the middle.
• If the list length is odd, skips the middle element.
• Restores the first half of the list to its original order.
• Compares the reversed first half with the second half of the list. If all corresponding elements are equal, the list is a palindrome.

3. printList Function

The printList function is a utility to print out the values of the linked list for demonstration purposes.

4. Main Function

The main function demonstrates the usage of the isPalindrome function:

• Creates a sample linked list that is a palindrome: 1 -> 2 -> 3 -> 2 -> 1.
• Prints the linked list.
• Checks if the list is a palindrome and prints the result.