Single linked list palindrome

Problem

Determine whether or not the single linked list is a palindrome.

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
}