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

目录

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/