[LeetCode] 382. Linked List Random Node

崔晓明发布于2019-08-16 13:47 / 808人阅读

Problem

Given a singly linked list, return a random node"s value from the linked list. Each node must have the same probability of being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

Solution

class Solution {

    /** @param head The linked list"s head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    ListNode head;
    Random random;
    public Solution(ListNode head) {
        this.head = head;
        random = new Random();
    }
    
    /** Returns a random node"s value. */
    public int getRandom() {
        ListNode cur = head;
        int res = cur.val, count = 1;
        while (cur.next != null) {
            cur = cur.next;
            if (random.nextInt(count+1) == count) {
                res = cur.val;
            }
            count++;
        }
        return res;
    }
}

GPU云服务器云服务器 linked LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72335.html

leetcode382. Linked List Random Node

摘要：题目要求要求从单链表中，随机返回一个节点的值，要求每个节点被选中的概率是相等的。假如一共有个物品，需要从其中挑选出个物品，要求确保个物品中每个物品都能够被等概率选中。对于这种等概率问题，简答的做法是通过随机数获取选中物品的下标。题目要求 Given a singly linked list, return a random nodes value from the linked li...

xiaodao 2019-08-16 17:58 评论0 收藏0
LeetCode[138] Copy List with Random Pointer

LeetCode[138] Copy List with Random Pointer A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of t...

novo 2019-08-14 15:57 评论0 收藏0
[LintCode/LeetCode] Copy List with Random Pointer

摘要：大体意思就是，先复制到，顺便将所有的放在再复制所有的到，顺便将所有的放在最后令，令，将和分离，返回的头结点 Problem A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. ...

Jacendfeng 2019-08-14 15:32 评论0 收藏0
[Leetcode] Copy List with Random Pointer 复制随机指针

摘要：栈迭代复杂度时间空间如果不算新链表的空间则是思路由于随机指针有可能产生环路，我们不能直接沿着随机指针的方向一个一个复制。同时我们又不能沿着指针直接复制，因为我们不知道随机指针所指向的新节点是哪个。 Copy List with Random Pointer A linked list is given such that each node contains an additiona...

Olivia 2019-08-14 12:25 评论0 收藏0
LeetCode 138：复制带随机指针的链表 Copy List with Random Poin

摘要：给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。提示你必须返回给定头的拷贝作为对克隆列表的引用。确定随机节点的关系之后再拆分链表。其时间复杂度为，空间复杂度为。给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。 A linked list is g...

entner 2019-08-19 10:13 评论0 收藏0