Palindrome Linked List

View the original problem on LeetCode

Implementation#

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    fast, slow := head, head

    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }

    fast = head
    slow = reverse(slow)

    for slow != nil {
        if slow.Val != fast.Val {
            return false
        }
        slow = slow.Next
        fast = fast.Next
    }

    return true
}


func reverse(head *ListNode) *ListNode {
    var prevNode *ListNode

    for head != nil {
        nextNode := head.Next
        head.Next = prevNode
        prevNode = head
        head = nextNode
    }

    return prevNode
}