328. 奇偶链表 Odd Even Linked-list
给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
示例 1:
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
示例 2:
输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
提示:
n ==链表中的节点数0 <= n <= 10^4-10^6 <= Node.val <= 10^6
代码：
package main import "fmt" type ListNode struct { Val int Next *ListNode } func oddEvenList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } oddHead := head evenHead := head.Next odd := oddHead even := evenHead for even != nil && even.Next != nil { odd.Next = even.Next odd = odd.Next even.Next = odd.Next even = even.Next } odd.Next = evenHead return oddHead } func buildList(list []int) *ListNode { head := &ListNode{Val: 0} for i := len(list) - 1; i >= 0; i-- { p := &ListNode{Val: list[i]} p.Next = head.Next head.Next = p } return head.Next } func printList(head *ListNode) { curr := head for curr != nil { fmt.Printf("%d->", curr.Val) curr = curr.Next } fmt.Println("nil") } func main() { nums := []int{1, 2, 3, 4, 5} head := buildList(nums) printList(head) head = oddEvenList(head) printList(head) nums = []int{2, 1, 3, 5, 6, 4, 7} head = buildList(nums) printList(head) head = oddEvenList(head) printList(head) }
输出：
1->2->3->4->5->nil
1->3->5->2->4->nil
2->1->3->5->6->4->7->nil
2->3->6->7->1->5->4->nil
382. 链表随机节点 Llinked-list Random Node
给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
实现 Solution 类：
Solution(ListNode head)使用整数数组初始化对象。int getRandom()从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
示例：
输入
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
输出
[null, 1, 3, 2, 2, 3]
解释
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
// getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。
提示：
- 链表中的节点数在范围
[1, 10^4]内 -10^4 <= Node.val <= 10^4- 至多调用
getRandom方法10^4次
进阶：
- 如果链表非常大且长度未知，该怎么处理？
- 你能否在不使用额外空间的情况下解决此问题？
代码：
package main import ( "fmt" "math/rand" ) type ListNode struct { Val int Next *ListNode } type Solution struct { head *ListNode } func Constructor(nums []int) Solution { dummy := &ListNode{} curr := dummy for _, num := range nums { node := &ListNode{Val: num} curr.Next = node curr = curr.Next } return Solution{head: dummy.Next} } func (s *Solution) GetRandom() int { curr := s.head count := 1 result := curr.Val for curr != nil { if rand.Intn(count) == 0 { result = curr.Val } curr = curr.Next count++ } return result } func main() { solution := Constructor([]int{1, 2, 3}) fmt.Println(solution.GetRandom()) fmt.Println(solution.GetRandom()) fmt.Println(solution.GetRandom()) fmt.Println(solution.GetRandom()) }
输出：
1
3
2
2
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：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）暂停更 |
