{"id":2151,"date":"2018-03-17T01:00:39","date_gmt":"2018-03-17T08:00:39","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2151"},"modified":"2018-03-17T01:01:18","modified_gmt":"2018-03-17T08:01:18","slug":"leetcode-382-linked-list-random-node","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/list\/leetcode-382-linked-list-random-node\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 382. Linked List Random Node"},"content":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u5199\u4e00\u4e2a\u65b9\u6cd5\u8fd4\u56de\u5217\u8868\u4e2d\u7684\u968f\u673a\u5143\u7d20\u3002<\/p>\n<h1>Problem:<\/h1>\n<p><a href=\"https:\/\/leetcode.com\/problems\/linked-list-random-node\/description\/\">https:\/\/leetcode.com\/problems\/linked-list-random-node\/description\/<\/a><\/p>\n<p>Given a singly linked list, return a random node&#8217;s value from the linked list. Each node must have the\u00a0<b>same probability<\/b>\u00a0of being chosen.<\/p>\n<p><b>Follow up:<\/b><br \/>\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<p><b>Example:<\/b><\/p>\n<pre class=\"lang:java decode:true\">\/\/ Init a singly linked list [1,2,3].\r\nListNode head = new ListNode(1);\r\nhead.next = new ListNode(2);\r\nhead.next.next = new ListNode(3);\r\nSolution solution = new Solution(head);\r\n\r\n\/\/ getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.\r\nsolution.getRandom();<\/pre>\n<h1>Solution:<\/h1>\n<p>C++<\/p>\n<p>Time Complexity: O(n)<\/p>\n<p>Space Complexity: O(1)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 43 ms\r\nclass Solution {\r\npublic:\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  Solution(ListNode* head) {\r\n    head_ = head;\r\n    \r\n    n_ = 0;\r\n    ListNode* curr = head;\r\n    while (curr != nullptr) {\r\n      curr = curr-&gt;next;\r\n      ++n_;\r\n    }\r\n  }\r\n\r\n  \/** Returns a random node's value. *\/\r\n  int getRandom() {\r\n    int n = rand() % n_;\r\n    ListNode* curr = head_;\r\n    while (n--&gt;0)\r\n      curr = curr-&gt;next;      \r\n    \r\n    return curr-&gt;val;\r\n  }\r\nprivate:\r\n  int n_;\r\n  \r\n   \/\/ Does not own the object\r\n  ListNode* head_;\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u5199\u4e00\u4e2a\u65b9\u6cd5\u8fd4\u56de\u5217\u8868\u4e2d\u7684\u968f\u673a\u5143\u7d20\u3002 Problem: https:\/\/leetcode.com\/problems\/linked-list-random-node\/description\/ Given a singly linked list, return a random node&#8217;s value from the linked list. Each node must have the\u00a0same probability\u00a0of being chosen.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[50],"tags":[83,177,91],"class_list":["post-2151","post","type-post","status-publish","format-standard","hentry","category-list","tag-list","tag-medium","tag-random","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2151","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2151"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2151\/revisions"}],"predecessor-version":[{"id":2153,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2151\/revisions\/2153"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2151"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2151"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2151"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}