Published on

# Single linked list palindrome

Authors

## 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
`_41func solution(l *ListNode) bool {_41 if l == nil || l.Next == nil {_41 return true_41 }_41_41 slow := l_41 fast := l_41_41 for fast.Next != nil && fast.Next.Next != nil {_41 slow = slow.Next_41 fast = fast.Next.Next _41 }_41_41 reverse := reverseList(slow.Next)_41 slow.Next = nil_41_41 for l != nil && reverse != nil {_41 if l.Value != reverse.Value {_41 return false_41 }_41 _41 l = l.Next_41 reverse = reverse.Next_41 }_41_41 return true_41}_41_41func reverseList(head *ListNode) *ListNode {_41 var prev *ListNode_41 current := head_41_41 for current != nil {_41 next := current.Next_41 current.Next = prev_41 prev = current_41 current = next_41 }_41_41 return prev_41}`