[Go版]算法通关村第一关白银——判断是否回文链表
题目:判断是否是回文链表
解决方法:快慢指针 递归反转链表
思路分析
- 使用快慢指针,当快指针到达结尾停下时,慢指针正好在中间(注意:奇数链表时,慢指针在正中间;偶数链表时,慢指针在中间的下一位)
- 然后反转此时的慢指针链表(比如:1->2->3->2->1,反转3->2->1,得到1(注意这个1是原链表的尾节点指针)->2->3)
- 最后循环反转后的链表和原链表,依次取出首节点对比,值不等说明不是回文序列,直达循环结束,结束条件是反转链表遍历完,如果到结束都是相等的,说明就是回文序列
复杂度:时间复杂度: O ( n ) O(n) O(n)、空间复杂度: O ( 1 ) O(1) O(1)
- 时间复杂度: O ( n ) O(n) O(n)
isPalindrome 函数的时间复杂度是 O ( n ) O(n) O(n),其中 n 是输入链表中节点的个数。这是因为该函数首先使用快慢指针技巧找到链表的中间节点,这需要 O ( n / 2 ) O(n/2) O(n/2) 的时间。然后,它递归地反转链表的后半部分,这也需要 O ( n / 2 ) O(n/2) O(n/2) 的时间。最后,它比较原始链表和反转链表中每个节点的值,这需要 O ( n ) O(n) O(n) 的时间。总的时间复杂度为 O ( n / 2 ) O(n/2) O(n/2) O ( n / 2 ) O(n/2) O(n/2) O ( n ) O(n) O(n)= O ( n ) O(n) O(n)。
- 空间复杂度: O ( 1 ) O(1) O(1)
isPalindrome 函数的空间复杂度是 O ( 1 ) O(1) O(1),因为它仅使用常量级别的额外空间来存储变量和指针,与输入链表的大小无关。递归的 reverselist 函数在进行递归过程中只存储临时变量,不使用与输入规模成比例的额外数据结构。因此,空间复杂度为 O ( 1 ) O(1) O(1)。
Go代码
import (
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
func reverselist(head *ListNode) *ListNode {
fmt.Println("reverse:", head.Val)
if head == nil || head.Next == nil {
return head
}
tmp := head
newHead := reverselist(tmp.Next)
tmp.Next.Next = tmp
tmp.Next = nil
return newHead
}
func isPalindrome(head *ListNode) bool {
if head == nil {
return false
}
if head.Next == nil {
return true
}
slow := head
fast := head
var newList *ListNode
for {
if fast == nil || fast.Next == nil{
break
}
slow = slow.Next
fast = fast.Next.Next
}
newList = reverselist(slow)
isSame := true
for {
if newList == nil || head == nil {
break
}
if newList.Val != head.Val {
isSame = false
break
}
newList = newList.Next
head = head.Next
}
return isSame
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgbhbbh
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01