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

The first use of linked lists in their modern form seems to have been by Peter Luhn in 1953, when he implemented a chaining-based hash table on the IBM 701 machine. Linked lists are often misattributed as being due to Newell et al. during their development of the IPL language (an early version of lisp), but that wasn't until 1956. The IPL language did ...


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

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

Consider a list and let $e,f,g$ be three consecutive elements. Each element stores a value and has a "forward" pointer to the next element. Additionally, if the list is doubly linked each element also has a "backward" pointer to the previous element. Consider a singly linked list first. If you want to delete element $f$, then you need to ...


1

No, you have to add additional information. There is no way to meet your requirements without adding additional information.


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

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