目录
234. 回文链表 Palindrome Linked-list 🌟
237. 删除链表中的节点 Delete Node In a Linked-list 🌟🌟
🌟 每日一练刷题专栏 🌟
Rust每日一练 专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
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）暂停更 |
