题目描述
请判断一个链表是否为回文链表。
示例1:
输入: 1->2
输出: false示例2:
输入: 1->2->2->1
输出: true进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解题思路
思路1
- 遍历链表,用数组存下每个节点的值,然后从数组两头开始向中间遍历,是否相等
- 时间复杂度O(n),空间复杂度O(n)
思路2
- 遍历一遍链表,得到链表长度n,根据长度的奇偶,找到中间节点,将左半边的链表反转,然后从中间节点分两个方向向左右两边遍历,是否是回文;对左半部分链表进行反转,还原为最初的链表
- 只需要固定的若干个临时变量,不需要额外开辟空间
- 时间复杂度为O(n),空间复杂度为O(1)
代码实现
// ListNode Definition for singly-linked list.
type ListNode struct {Val intNext *ListNode
}// 解法1
// 用数组存前面的一半节点的值
// 时间复杂度：O(N)
// 空间复杂度：O(N)
func isPalindrome(head *ListNode) bool {// 空链表,算回文if head == nil {return true}var data []intfor cur := head; cur != nil; cur = cur.Next {data = append(data, cur.Val)}for i, j := 0, len(data)-1; i <= j; {if data[i] != data[j] {return false}i++j--}return true
}// 解法2
// 找到链表中间节点，将前半部分转置，再从中间向左右遍历对比
// 时间复杂度：O(N)
// 空间复杂度：O(1)
func isPalindrome2(head *ListNode) bool {if head == nil || head.Next == nil {return true}isPalindrome := true//链表长度length := 0for cur := head; cur != nil; cur = cur.Next {length++}//将前半部分反转step := length / 2var prev *ListNodecur := headfor i := 1; i <= step; i++ {cur.Next, prev, cur = prev, cur, cur.Next}mid := curvar left, right *ListNode = prev, nilif length%2 == 0 {//长度为偶数right = mid} else {right = mid.Next}//从中间向左右两边遍历对比for left != nil && right != nil {if left.Val != right.Val {//值不相等,不是回文链表isPalindrome = falsebreak}left = left.Nextright = right.Next}//将前半部分反转的链表进行复原cur = prevprev = midfor cur != nil {cur.Next, prev, cur = prev, cur, cur.Next}return isPalindrome
}GitHub
- 源码传送门
- 项目中会提供各种数据结构及算法的Golang实现, LeetCode解题思路及答案
题目来源
leetcode 234. 回文链表
