Losing head/tail while rewiring
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
Move from brute-force thinking to an efficient approach using linked list strategy.
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.
Implement the Solution class:
Solution(ListNode head) Initializes the object with the head of the singly-linked list head.int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.Example 1:
Input ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []] Output [null, 1, 3, 2, 2, 3] Explanation Solution solution = new Solution([1, 2, 3]); solution.getRandom(); // return 1 solution.getRandom(); // return 3 solution.getRandom(); // return 2 solution.getRandom(); // return 2 solution.getRandom(); // return 3 // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
Constraints:
[1, 104].-104 <= Node.val <= 104104 calls will be made to getRandom.Follow up:
Problem summary: 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. Implement the Solution class: Solution(ListNode head) Initializes the object with the head of the singly-linked list head. int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Linked List · Math
["Solution","getRandom","getRandom","getRandom","getRandom","getRandom"] [[[1,2,3]],[],[],[],[],[]]
random-pick-index)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #382: Linked List Random Node
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
private ListNode head;
private Random random = new Random();
public Solution(ListNode head) {
this.head = head;
}
public int getRandom() {
int ans = 0, n = 0;
for (ListNode node = head; node != null; node = node.next) {
++n;
int x = 1 + random.nextInt(n);
if (n == x) {
ans = node.val;
}
}
return ans;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/
// Accepted solution for LeetCode #382: Linked List Random Node
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
type Solution struct {
head *ListNode
}
func Constructor(head *ListNode) Solution {
return Solution{head}
}
func (this *Solution) GetRandom() int {
n, ans := 0, 0
for node := this.head; node != nil; node = node.Next {
n++
x := 1 + rand.Intn(n)
if n == x {
ans = node.Val
}
}
return ans
}
/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(head);
* param_1 := obj.GetRandom();
*/
# Accepted solution for LeetCode #382: Linked List Random Node
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def __init__(self, head: Optional[ListNode]):
self.head = head
def getRandom(self) -> int:
n = ans = 0
head = self.head
while head:
n += 1
x = random.randint(1, n)
if n == x:
ans = head.val
head = head.next
return ans
# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()
// Accepted solution for LeetCode #382: Linked List Random Node
use rand::prelude::*;
use rustgym_util::*;
struct Solution {
head: ListLink,
rng: ThreadRng,
}
impl Solution {
fn new(head: ListLink) -> Self {
let rng = thread_rng();
Solution { head, rng }
}
fn get_random(&mut self) -> i32 {
let mut cur = &self.head;
let mut res = 0;
let mut count = 0;
while let Some(node) = cur {
let val = node.val;
count += 1;
if self.rng.gen_range(0, count) == 0 {
res = val;
}
cur = &node.next;
}
res
}
}
// Accepted solution for LeetCode #382: Linked List Random Node
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #382: Linked List Random Node
// /**
// * Definition for singly-linked list.
// * public class ListNode {
// * int val;
// * ListNode next;
// * ListNode() {}
// * ListNode(int val) { this.val = val; }
// * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// * }
// */
// class Solution {
// private ListNode head;
// private Random random = new Random();
//
// public Solution(ListNode head) {
// this.head = head;
// }
//
// public int getRandom() {
// int ans = 0, n = 0;
// for (ListNode node = head; node != null; node = node.next) {
// ++n;
// int x = 1 + random.nextInt(n);
// if (n == x) {
// ans = node.val;
// }
// }
// return ans;
// }
// }
//
// /**
// * Your Solution object will be instantiated and called as such:
// * Solution obj = new Solution(head);
// * int param_1 = obj.getRandom();
// */
Use this to step through a reusable interview workflow for this problem.
Copy all n nodes into an array (O(n) time and space), then use array indexing for random access. Operations like reversal or middle-finding become trivial with indices, but the O(n) extra space defeats the purpose of using a linked list.
Most linked list operations traverse the list once (O(n)) and re-wire pointers in-place (O(1) extra space). The brute force often copies nodes to an array to enable random access, costing O(n) space. In-place pointer manipulation eliminates that.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.