# Tag Info

4

There is a surprisingly simpler solution! Are you familiar with the tortoise and hare algorithm? Start thinking from there: Understand this algorithm and why it works, and then you might get an idea or two for the problem

3

You can use a disjoint sets data structure to quickly solve your problem (exercise). This can be further improved by exploiting the particular nature of your problem. We maintain a list of intervals $[a_1,b_1],[a_2,b_2],\ldots$ which succinctly represent the integers seen so far. In addition, we store $a_i,b_i$ in a hash table. Given a new integer $c$, we ...

2

The easiest way to understand this is really to draw it out and move your fingers on a graph, so I recommend literally pulling out a piece of paper to follow along. Picture the part before the cycle as a line, and the cycle is a circle. So we have a straight line of arrows pointing into a circle of arrows. The length of the line is X steps, and the length of ...

2

Yes, there are many types of lists depending on the arrangement of objects and the complexity of different types of operations. For example: Binary Tree or d-ary tree is a hierarchical structure that stores nodes in the form of parent and child nodes. Directed or Undirected Graph can be represented using adjacency list data structure which represents all ...

2

When processing a node, follow the unique outgoing path until reaching a node with two children, and only then recurse. In pseudocode: process-all(node v): loop process v split into cases according to the number of children that v has: no children: quit the entire procedure one child: replace v with its unique child two children: ...

1

1

In terms of computational complexity, both approaches will be $O(n)$. Also, its impossible to do better than $O(n)$, since you must always go through all elements in the linked-list anyways. So in those terms, the running times are equivalent. What about the space (memory) complexity? Well, in both cases we ultimately create an array of length $n$ and ...

1

It seems this paper, which serves as a foundation for subsequent work on list ranking parallel algorithms, handles the oversight of assigning processors by assuming that the input is just given as an array containing the linked list (not necessarily in the order of the nodes in the list). This assumption of contiguous memory storage is implicitly followed in ...

1

A "list" or "sequence" is an ordered collection of elements. So there are a lot of lists. In addition to an Array and a Linked List: Doubly Linked List https://en.wikipedia.org/wiki/Doubly_linked_list (including XOR linked list) Unrolled Linked List https://en.wikipedia.org/wiki/Unrolled_linked_list K-ary tree (including Binary Tree) ...

1

First of all, let me strongly recommend avoiding outdated textbooks such as Aho, Hopcroft and Ullman. Let me also replace Aho, Hopcroft and Ullman's use of "position" with the more common notion of pointer. In a linked list, each cell consists of a value and pointer to the following cell (if any). The linked list itself is represented as a pointer ...

1

I try to draw function curves to see what happen when two pointers velocities are not 2:1，and verified the correctness of finding the start of cycle. https://www.desmos.com/calculator/snqtvrmhn3

Only top voted, non community-wiki answers of a minimum length are eligible