题目描述
请判断一个链表是否为回文链表。
示例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 int Next *ListNode}// 解法1// 用数组存前面的一半节点的值// 时间复杂度：O(N)// 空间复杂度：O(N)func isPalindrome(head *ListNode) bool { // 空链表,算回文 if head == nil { return true } var data []int for 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 := 0 for cur := head; cur != nil; cur = cur.Next { length++ } //将前半部分反转 step := length / 2 var prev *ListNode cur := head for i := 1; i <= step; i++ { cur.Next, prev, cur = prev, cur, cur.Next } mid := cur var left, right *ListNode = prev, nil if length%2 == 0 { //长度为偶数 right = mid } else { right = mid.Next } //从中间向左右两边遍历对比 for left != nil && right != nil { if left.Val != right.Val { //值不相等,不是回文链表 isPalindrome = false break } left = left.Next right = right.Next } //将前半部分反转的链表进行复原 cur = prev prev = mid for cur != nil { cur.Next, prev, cur = prev, cur, cur.Next } return isPalindrome}复制代码 GitHub
- 项目中会提供各种数据结构及算法的Golang实现, LeetCode解题思路及答案