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）暂停更 |
