LeetCode-in-All

234. Palindrome Linked List

Easy

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]

Output: true

Example 2:

Input: head = [1,2]

Output: false

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

Solution

type ListNode struct {
	Val  int
	Next *ListNode
}

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

	// Reverse the right half of the list
	len /= 2
	right = head
	for i := 0; i < len; i++ {
		right = right.Next
	}
	var prev *ListNode
	for right != nil {
		next := right.Next
		right.Next = prev
		prev = right
		right = next
	}

	// Compare left half and right half
	for i := 0; i < len; i++ {
		if prev != nil && head.Val == prev.Val {
			head = head.Next
			prev = prev.Next
		} else {
			return false
		}
	}
	return true
}

This site is open source. Improve this page.