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.<\/p>\n
Follow up:
\nWhat if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?<\/p>\n
Example:<\/p>\n
\/\/ Init a singly linked list [1,2,3].
\nListNode head = new ListNode(1);
\nhead.next = new ListNode(2);
\nhead.next.next = new ListNode(3);
\nSolution solution = new Solution(head);<\/p>\n
\/\/ getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
\nsolution.getRandom();<\/p>\n
\r\n\r\n\/**\r\n * Definition for singly-linked list.\r\n * function ListNode(val) {\r\n * this.val = val;\r\n * this.next = null;\r\n * }\r\n *\/\r\n\/**\r\n * @param head The linked list's head.\r\n Note that the head is guaranteed to be not null, so it contains at least one node.\r\n * @param {ListNode} head\r\n *\/\r\nvar Solution = function(head) {\r\n this.head = head;\r\n};\r\n\r\n\/**\r\n * Returns a random node's value.\r\n * @return {number}\r\n *\/\r\nSolution.prototype.getRandom = function() {\r\n \r\n var total = 1;\r\n var p = this.head;\r\n while(p.next !== null){\r\n p = p.next;\r\n total++;\r\n }\r\n \r\n var index = Math.floor(Math.random() * Math.floor(total))\r\n var p = this.head;\r\n for(var i=0;i<index;i++){\r\n p = p.next;\r\n }\r\n \r\n return p.val;\r\n \r\n};\r\n\r\n\/** \r\n * Your Solution object will be instantiated and called as such:\r\n * var obj = new Solution(head)\r\n * var param_1 = obj.getRandom()\r\n *\/\r\n\r\n<\/pre>\nRandom Set- Phone Interview
\nCompletedJune 1, 2019 7:41 AM
\nTime Spent: 38 minutes 29 seconds
\nTime Allotted: 1 hour 30 minutes
\nIn order to provide you a more accurate assessment, we are waiting for more users to take this interview.
\nEmail me when my report is ready
\nFind Pivot Index
\nEASY
\n741 \/ 741 Testcases Passed
\nDetails
\nLinked List Random Node
\nMEDIUM
\n7 \/ 7 Testcases Passed<\/p>\n","protected":false},"excerpt":{"rendered":"