234. Palindrome Linked List #

题目 #

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?

题目大意 #

判断一个链表是否是回文链表。要求时间复杂度 O(n)，空间复杂度 O(1)。

解题思路 #

这道题只需要在第 143 题上面改改就可以了。思路是完全一致的。先找到中间结点，然后反转中间结点后面到结尾的所有结点。最后一一判断头结点开始的结点和中间结点往后开始的结点是否相等。如果一直相等，就是回文链表，如果有不相等的，直接返回不是回文链表。

代码 #


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
 * }
 */

// 解法一
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
}

// 解法二
// 此题和 143 题 Reorder List 思路基本一致
func isPalindrome1(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}
	res := true
	// 寻找中间结点
	p1 := head
	p2 := head
	for p2.Next != nil && p2.Next.Next != nil {
		p1 = p1.Next
		p2 = p2.Next.Next
	}
	// 反转链表后半部分  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
	}
	// 扫描表，判断是否是回文
	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
}

⬅️上一页

下一页➡️