Tag Archives: Palindrome list

Leetcode-234: palindrome linked list

Topic describes
Determine whether a linked list is a palindrome list.
// 1 2 nil
// 1 2 1 nil
// 1 2 2 1 nil
Thought analysis
The fast and slow pointer finds the midpoint of the linked list and splits the midpoint and reverses the tail list to compare whether the values of the head and tail list are equal in turn
Code implementation

func isPalindrome(head *ListNode) bool {
	if head == nil {
		return true
	}
	fast := head.Next
	slow := head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}

	tail := reverse(slow.Next)
	slow.Next = nil

	for head != nil && tail != nil {
		if head.Val != tail.Val {
			return false
		}
		head = head.Next
		tail = tail.Next
	}
	return true
}

func reverse(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	var pre *ListNode
	for head != nil {
		temp := head.Next
		head.Next = pre
		pre = head
		head = temp
	}
	return pre
}