Palindrome Linked List using Golang

 Palindrome Linked List using Golang

This solution first finds the middle of the linked list using a slow and fast pointer. It then reverses the second half of the linked list using a prev pointer. Finally, it compares the first and second half of the linked list to see if they are equal. If they are equal, then the linked list is a palindrome.


package main import "fmt" // Node represents a node in a linked list type Node struct { Val int Next *Node } // IsPalindrome checks if the linked list is a palindrome func IsPalindrome(head *Node) bool { if head == nil { return true } // Find the middle of the linked list slow := head fast := head for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next } // Reverse the second half of the linked list var prev *Node for slow != nil { next := slow.Next slow.Next = prev prev = slow slow = next } // Compare the first and second half of the linked list for prev != nil { if prev.Val != head.Val { return false } prev = prev.Next head = head.Next } return true } func main() { // Test cases tests := []struct { nums []int want bool }{ {[]int{1, 2, 3, 2, 1}, true}, {[]int{1, 2, 3, 4, 5}, false}, {[]int{1, 2, 2, 1}, true}, {[]int{1}, true}, {[]int{}, true}, } for _, test := range tests { // Create linked list var head *Node for i := len(test.nums) - 1; i >= 0; i-- { head = &Node{Val: test.nums[i], Next: head} } // Check if linked list is a palindrome got := IsPalindrome(head) if got != test.want { fmt.Printf("IsPalindrome(%v) = %t\n", test.nums, got) } } }



  1. Explain the problem: The problem is to check if a linked list is a palindrome, which means that it is the same forwards and backwards. For example, the linked list "1 -> 2 -> 3 -> 2 -> 1" is a palindrome, but the linked list "1 -> 2 -> 3 -> 4 -> 5" is not.

  2. Describe the overall strategy: The solution first finds the middle of the linked list using a slow and fast pointer. It then reverses the second half of the linked list using a prev pointer. Finally, it compares the first and second half of the linked list to see if they are equal. If they are equal, then the linked list is a palindrome.

  3. Walk through the code:

  • First, the function checks if the linked list is empty. If it is, it returns true because an empty linked list is considered to be a palindrome.
  • Next, the function initializes the slow and fast pointers to the head of the linked list. It then enters a loop that moves the slow pointer one node at a time and the fast pointer two nodes at a time. This loop continues until the fast pointer reaches the end of the linked list. This effectively finds the middle of the linked list.
  • After finding the middle of the linked list, the function reverses the second half of the linked list using a prev pointer. It starts with the slow pointer and initializes the prev pointer to nil. It then enters a loop that moves the slow pointer to the next node and reverses the next pointer of the slow pointer to point to the prev pointer. The prev pointer is then updated to be the current slow pointer. This loop continues until the slow pointer reaches the end of the second half of the linked list.
  • Finally, the function compares the first and second half of the linked list to see if they are equal. It does this by initializing two pointers, head and prev, to the head and the reversed second half of the linked list, respectively. It then enters a loop that compares the values of the head and prev pointers and moves both pointers to the next node. If any of the values are not equal, the function returns false. If the loop completes without returning false, the function returns true.
  1. Explain the test cases: The code includes several test cases that test the function with different input linked lists. The first test case checks a linked list that is a palindrome, the second test case checks a linked list that is not a palindrome, the third test case checks a linked list with an even number of elements that is a palindrome, the fourth test case checks a linked list with one element, and the fifth test case checks an empty linked list.

Post a Comment

0 Comments