234. Palindrome Linked List #

Problem #

Given a singly linked list, determine if it is a palindrome.

Example 1:


Input: 1->2
Output: false

Example 2:


Input: 1->2->2->1
Output: true

Follow up:

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

Problem Summary #

Determine whether a linked list is a palindrome linked list. The required time complexity is O(n), and the space complexity is O(1).

Solution Approach #

For this problem, you only need to make slight modifications based on Problem 143. The idea is exactly the same. First find the middle node, then reverse all nodes from after the middle node to the end. Finally, compare the nodes starting from the head node with the nodes starting from after the middle node one by one to see whether they are equal. If they are always equal, it is a palindrome linked list; if any pair is not equal, directly return that it is not a palindrome linked list.

Code #


package leetcode

import (
	"github.com/halfrost/leetcode-go/structures"
)

// ListNode define
type ListNode = structures.ListNode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// Solution 1
func isPalindrome(head *ListNode) bool {
	slice := []int{}
	for head != nil {
		slice = append(slice, head.Val)
		head = head.Next
	}
	for i, j := 0, len(slice)-1; i < j; {
		if slice[i] != slice[j] {
			return false
		}
		i++
		j--
	}
	return true
}

// Solution 2
// This problem has basically the same idea as Problem 143 Reorder List
func isPalindrome1(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}
	res := true
	// Find the middle node
	p1 := head
	p2 := head
	for p2.Next != nil && p2.Next.Next != nil {
		p1 = p1.Next
		p2 = p2.Next.Next
	}
	// Reverse the second half of the linked list  1->2->3->4->5->6 to 1->2->3->6->5->4
	preMiddle := p1
	preCurrent := p1.Next
	for preCurrent.Next != nil {
		current := preCurrent.Next
		preCurrent.Next = current.Next
		current.Next = preMiddle.Next
		preMiddle.Next = current
	}
	// Scan the list to determine whether it is a palindrome
	p1 = head
	p2 = preMiddle.Next
	// fmt.Printf("p1 = %v p2 = %v preMiddle = %v head = %v\n", p1.Val, p2.Val, preMiddle.Val, L2ss(head))
	for p1 != preMiddle {
		// fmt.Printf("*****p1 = %v p2 = %v preMiddle = %v head = %v\n", p1, p2, preMiddle, L2ss(head))
		if p1.Val == p2.Val {
			p1 = p1.Next
			p2 = p2.Next
			// fmt.Printf("-------p1 = %v p2 = %v preMiddle = %v head = %v\n", p1, p2, preMiddle, L2ss(head))
		} else {
			res = false
			break
		}
	}
	if p1 == preMiddle {
		if p2 != nil && p1.Val != p2.Val {
			return false
		}
	}
	return res
}

// L2ss define
func L2ss(head *ListNode) []int {
	res := []int{}
	for head != nil {
		res = append(res, head.Val)
		head = head.Next
	}
	return res
}