Solve Linked-List and Iterator Problems

You are asked to solve two coding problems.

Problem 1: Detect shared nodes between possibly cyclic linked lists

You are given the heads of two singly linked lists. Each list may be acyclic or may contain a cycle. A node is considered shared only if it is the exact same object/reference in memory, not merely a node with the same value.

Implement:

def share_any_node(head_a: Optional[Node], head_b: Optional[Node]) -> bool:
 pass

Return True if the two lists share at least one node; otherwise return False.

A Node has the following structure:

class Node:
 def __init__(self, value):
 self.value = value
 self.next = None

Consider all structural cases:

• Both lists are acyclic.
• One list is cyclic and the other is acyclic.
• Both lists are cyclic but have completely separate cycles.
• Both lists are cyclic and eventually enter the same cycle.
• Both lists are cyclic and have the same cycle entry.
• Both lists are cyclic and have different cycle entries but share the same cycle.

Follow-up:

def find_shared_node(head_a: Optional[Node], head_b: Optional[Node]) -> Optional[Node]:
 pass

Return any shared node if one exists; otherwise return None. If the only shared nodes are inside a common cycle, returning any node in that shared cycle is acceptable.

Discuss the expected time and space complexity.

Problem 2: Implement a round-robin multi-stream iterator

You are given multiple input streams. Each stream is an iterator over bytes or characters and supports:

has_next() -> bool
next() -> value

Implement a RoundRobinIterator that merges these streams in round-robin order.

Example:

stream 1: A B C
stream 2: x y
stream 3: 1 2 3 4

output: A x 1 B y 2 C 3 4

Rules:

• On each call to next(), return one element from the next available stream.
• If a stream is exhausted, skip it for all future calls.
• has_next() should return whether any stream still has data.
• has_next() should be safe to call multiple times without consuming elements.
• next() should raise an appropriate exception if no elements remain.
• Do not read all stream contents into memory up front.
• Preserve the provided interface and method signatures exactly if a base iterator class is supplied.