Single linked list palindrome

February 2, 2023

Moch Lutfi
Name
Moch Lutfi
Twitter
@kaptenupi

Problem

Determine whether or not the single linked list is a palindrome (opens in a new tab).

Solution

In the single linked list case determine palindrome is tricky, because the node only forward and the size is uknown without iterate through the linked list. That means you can't know whether a linked list is palindrome or not without traversing through the linked list.

  • Find the center point of the node list, using double steps (fast var) and reverse the first half of the list.
  • Walk on the second half and walk back in the first to the first difference.
  • Return false if found diff, or true if all items are equal.
solution.go

func solution(l *ListNode) bool {
if l == nil || l.Next == nil {
return true
}
slow := l
fast := l
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
reverse := reverseList(slow.Next)
slow.Next = nil
for l != nil && reverse != nil {
if l.Value != reverse.Value {
return false
}
l = l.Next
reverse = reverse.Next
}
return true
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
current := head
for current != nil {
next := current.Next
current.Next = prev
prev = current
current = next
}
return prev
}