Palindrome Linked List

1. Problem Description

Determine whether a linked list is a palindrome.

2. Approach

1. Approach 1
   • Traverse the linked list and store the values in an array
   • Use two pointers to determine whether the array is a palindrome
2. Approach 2
   1. Traverse twice
   2. Reverse the second half of the linked list
3. Approach 3
   • Fast and slow pointers
   • Move the fast pointer two steps and the slow pointer one step until the fast pointer reaches the end; at that point the slow pointer is around the middle of the list
   • Reverse the second half of the linked list
   • Traverse the two lists from the beginning and compare whether they are equal

3. Implementation

3.1. Stack

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    stack := make([]int, 0)
    current := head
    for current != nil {
        stack = append(stack, current.Val)
        current = current.Next
    }

    left := 0
    right := len(stack)-1
    for left < right {
        if stack[left] != stack[right] {
            return false
        }
        left++
        right--
    }

    return true
}

3.2. Two Passes + Reverse the Second Half

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    count := 0
    h := head
    for h != nil {
        count++
        h = h.Next
    }

    h = head
    for i := 0; i < count/2; i++ {
        h = h.Next
    }
    l2 := reverseList(h)
    l1 := head
    for l1 != nil && l2 != nil {
        if l1.Val != l2.Val {
            return false
        }
        l1 = l1.Next
        l2 = l2.Next
    }

    return true
}

func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    current := head
    var next *ListNode
    for current != nil {
        next = current.Next
        current.Next = pre
        pre = current
        current = next
    }
 
    return pre
}

3.3. Fast/Slow Pointers + Reverse the Second Half

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    fast := head
    slow := head
    for fast != nil && fast.Next != nil{
        fast = fast.Next.Next
        slow = slow.Next
    }
    head2 := reverseList(slow)
    for head != nil && head2 != nil {
        if head.Val != head2.Val {
            return false
        }
        head = head.Next
        head2 = head2.Next
    }
    return true
}

func reverseList(head *ListNode)*ListNode {
    var prev *ListNode
    current := head
    var next *ListNode
    for current != nil {
        next = current.Next
        current.Next = prev
        prev = current
        current = next
    } 
    return prev
}

4. References

• 234. Palindrome Linked List - LeetCode