Golang每日一练(leetDay0086) 回文链表、删除链表节点

简介: Golang每日一练(leetDay0086) 回文链表、删除链表节点

234. 回文链表 Palindrome Linked-list

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false

示例 1:

输入:head = [1,2,2,1]

输出:true


示例 2:

输入:head = [1,2]

输出:false


提示:

  • 链表中节点数目在范围[1, 10^5]
  • 0 <= Node.val <= 9

进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

代码1:

package main
import "fmt"
type ListNode struct {
  Val  int
  Next *ListNode
}
func isPalindrome(head *ListNode) bool {
  if head == nil {
    return true
  }
  slow, fast := head, head
  var stack []int
  for fast != nil && fast.Next != nil {
    stack = append(stack, slow.Val)
    slow = slow.Next
    fast = fast.Next.Next
  }
  // odd length
  if fast != nil {
    slow = slow.Next
  }
  for slow != nil {
    if len(stack) == 0 || slow.Val != stack[len(stack)-1] {
      return false
    }
    stack = stack[:len(stack)-1]
    slow = slow.Next
  }
  return true
}
func createLinkedList(nums []int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{Val: nums[0]}
  cur := head
  for i := 1; i < len(nums); i++ {
    cur.Next = &ListNode{Val: nums[i]}
    cur = cur.Next
  }
  return head
}
func printLinkedList(head *ListNode) {
  cur := head
  for cur != nil {
    fmt.Print(cur.Val, "->")
    cur = cur.Next
  }
  fmt.Println("nil")
}
func main() {
  nums := []int{1, 2, 2, 1}
  head := createLinkedList(nums)
  printLinkedList(head)
  fmt.Println(isPalindrome(head))
  nums = []int{1, 2}
  head = createLinkedList(nums)
  printLinkedList(head)
  fmt.Println(isPalindrome(head))
}

代码2:

package main
import "fmt"
type ListNode struct {
  Val  int
  Next *ListNode
}
func isPalindrome(head *ListNode) bool {
    if head == nil {
        return true
    }
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    var prev *ListNode
    for slow != nil {
        next := slow.Next
        slow.Next = prev
        prev = slow
        slow = next
    }
    for prev != nil && head != nil {
        if prev.Val != head.Val {
            return false
        }
        prev = prev.Next
        head = head.Next
    }
    return true
}
func createLinkedList(nums []int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{Val: nums[0]}
  cur := head
  for i := 1; i < len(nums); i++ {
    cur.Next = &ListNode{Val: nums[i]}
    cur = cur.Next
  }
  return head
}
func printLinkedList(head *ListNode) {
  cur := head
  for cur != nil {
    fmt.Print(cur.Val, "->")
    cur = cur.Next
  }
  fmt.Println("nil")
}
func main() {
  nums := []int{1, 2, 2, 1}
  head := createLinkedList(nums)
  printLinkedList(head)
  fmt.Println(isPalindrome(head))
  nums = []int{1, 2}
  head = createLinkedList(nums)
  printLinkedList(head)
  fmt.Println(isPalindrome(head))
}

代码3:

package main
import "fmt"
type ListNode struct {
  Val  int
  Next *ListNode
}
var left *ListNode
func isPalindrome(head *ListNode) bool {
  left = head
  return traverse(head)
}
func traverse(right *ListNode) bool {
  if right == nil {
    return true
  }
  res := traverse(right.Next)
  res = res && (left.Val == right.Val)
  left = left.Next
  return res
}
func createLinkedList(nums []int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{Val: nums[0]}
  cur := head
  for i := 1; i < len(nums); i++ {
    cur.Next = &ListNode{Val: nums[i]}
    cur = cur.Next
  }
  return head
}
func printLinkedList(head *ListNode) {
  cur := head
  for cur != nil {
    fmt.Print(cur.Val, "->")
    cur = cur.Next
  }
  fmt.Println("nil")
}
func main() {
  nums := []int{1, 2, 2, 1}
  head := createLinkedList(nums)
  printLinkedList(head)
  fmt.Println(isPalindrome(head))
  nums = []int{1, 2}
  head = createLinkedList(nums)
  printLinkedList(head)
  fmt.Println(isPalindrome(head))
}

输出:

1->2->2->1->nil

true

1->2->nil

false


237. 删除链表中的节点 Delete Node In a Linked-list

请编写一个函数,用于 删除单链表中某个特定节点 。在设计函数时需要注意,你无法访问链表的头节点 head ,只能直接访问 要被删除的节点

题目数据保证需要删除的节点 不是末尾节点

示例 1:

输入:head = [4,5,1,9], node = 5

输出:[4,1,9]

解释:指定链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9


示例 2:

输入:head = [4,5,1,9], node = 1

输出:[4,5,9]

解释:指定链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9


提示:

  • 链表中节点的数目范围是 [2, 1000]
  • -1000 <= Node.val <= 1000
  • 链表中每个节点的值都是 唯一
  • 需要删除的节点 node链表中的节点 ,且 不是末尾节点

代码:

package main
import "fmt"
type ListNode struct {
  Val  int
  Next *ListNode
}
func deleteNode(node *ListNode) {
  node.Val = node.Next.Val
  node.Next = node.Next.Next
}
func printLinkedList(head *ListNode) {
  cur := head
  for cur != nil {
    fmt.Print(cur.Val, "->")
    cur = cur.Next
  }
  fmt.Println("nil")
}
func main() {
  node1 := &ListNode{4, nil}
  node2 := &ListNode{5, nil}
  node3 := &ListNode{1, nil}
  node4 := &ListNode{9, nil}
  node1.Next = node2
  node2.Next = node3
  node3.Next = node4
  deleteNode(node2)
  printLinkedList(node1)
  node1 = &ListNode{4, nil}
  node2 = &ListNode{5, nil}
  node3 = &ListNode{1, nil}
  node4 = &ListNode{9, nil}
  node1.Next = node2
  node2.Next = node3
  node3.Next = node4
  deleteNode(node3)
  printLinkedList(node1)
}

输出:

4->1->9->nil

4->5->9->nil


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力!

🌟 收藏,你的青睐是我努力的方向!

评论,你的意见是我进步的财富!  

主页:https://hannyang.blog.csdn.net/

Rust每日一练 专栏

(2023.5.16~)更新中...

Golang每日一练 专栏

(2023.3.11~)更新中...

Python每日一练 专栏

(2023.2.18~2023.5.18)暂停更

C/C++每日一练 专栏

(2023.2.18~2023.5.18)暂停更

Java每日一练 专栏

(2023.3.11~2023.5.18)暂停更


目录
相关文章
|
14天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
18 0
【数据结构OJ题】链表的回文结构
|
29天前
|
算法 C语言
【数据结构与算法 经典例题】链表的回文结构(图文详解)
【数据结构与算法 经典例题】链表的回文结构(图文详解)
|
1月前
|
Go
Go语言每日一练链表篇(一)
Go语言每日一练链表篇(一)
|
1月前
|
算法 容器
【LeetCode刷题】快乐数、盛水最多的容器
【LeetCode刷题】快乐数、盛水最多的容器
|
2月前
题目----力扣--回文链表
题目----力扣--回文链表
25 0
|
2月前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
24 0
|
2月前
|
算法
【每日一题】牛客网——链表的回文结构
【每日一题】牛客网——链表的回文结构
|
2月前
|
监控 算法 Go
Golang深入浅出之-Go语言中的服务熔断、降级与限流策略
【5月更文挑战第4天】本文探讨了分布式系统中保障稳定性的重要策略:服务熔断、降级和限流。服务熔断通过快速失败和暂停故障服务调用来保护系统;服务降级在压力大时提供有限功能以保持整体可用性;限流控制访问频率,防止过载。文中列举了常见问题、解决方案,并提供了Go语言实现示例。合理应用这些策略能增强系统韧性和可用性。
175 0
|
2月前
|
前端开发 Go
Golang深入浅出之-Go语言中的异步编程与Future/Promise模式
【5月更文挑战第3天】Go语言通过goroutines和channels实现异步编程,虽无内置Future/Promise,但可借助其特性模拟。本文探讨了如何使用channel实现Future模式,提供了异步获取URL内容长度的示例,并警示了Channel泄漏、错误处理和并发控制等常见问题。为避免这些问题,建议显式关闭channel、使用context.Context、并发控制机制及有效传播错误。理解并应用这些技巧能提升Go语言异步编程的效率和健壮性。
116 5
Golang深入浅出之-Go语言中的异步编程与Future/Promise模式
|
2月前
|
Prometheus 监控 Cloud Native
Golang深入浅出之-Go语言中的分布式追踪与监控系统集成
【5月更文挑战第4天】本文探讨了Go语言中分布式追踪与监控的重要性,包括追踪的三个核心组件和监控系统集成。常见问题有追踪数据丢失、性能开销和监控指标不当。解决策略涉及使用OpenTracing或OpenTelemetry协议、采样策略以及聚焦关键指标。文中提供了OpenTelemetry和Prometheus的Go代码示例,强调全面可观测性对微服务架构的意义,并提示选择合适工具和策略以确保系统稳定高效。
184 5