Detect Loop in Linked List

What is the best way to find out if a linked list contains a loop? You're given the following data structure as the definition of a linked list node:

class LinkedListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

A loop or a cycle in graph theory is a path of nodes and edges where a node is reachable from itself.

Implement a detectLoop method that takes a linked list head node as the parameter and returns true or false depending on whether there's a cycle.

Constraints

• Length of the linked list <= 10000
• Value stored in each node will be between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(1)

```js
function detectLoop(head) {
  // Fill in this method
  return head;
}

class LinkedListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

const list1 = new LinkedListNode(3);
const nodes = [4, 5, 6, 7, 8, 9, 10];
let head = list1;
for (let i = 0; i < nodes.length; i++) {
  const newNode = new LinkedListNode(nodes[i]);
  head.next = newNode;
  head = newNode;
}
list1.next.next.next.next.next.next = list1.next.next;
console.log(detectLoop(list1));
```

A walk is a sequence of at least two vertices where nodes and edges may repeat. A cycle is a sequence of at least two vertices where nodes and edges cannot repeat.

Image credit to https://www.includehelp.com

Usually linked lists end with a node with no next reference, but we're looking for a sequence with a next pointer to a previous node. What might be the brute force solution here?

```js
// 1 -> 3 <-> 5
//      |
//      7
```

In the above example, once we get to the second 3 node, how do we know we've got a cycle? We need some reference that we've previously encountered this vertex before.

What if we used a nested loop for tracking purposes? Let's take a look at what would happen in pseudocode:

```
iterate through 1 -> 3 -> 5 -> 3 -> 7
  iterate through what we've seen so far
```

At outer loop node 1, we'd inner loop through 1.

At outer loop node 3, we'd inner loop through 1 -> 3.

At outer loop node 5, we'd inner loop through 1 -> 3 -> 5.

At outer loop node 3 again, we'd inner loop through 1 -> 3 -> 5 -> 3.

So the brute force way to do it is to conduct a nested traversal-- we can traverse all the nodes, and then at each iteration, traverse through the nodes already visited by the outer loop. In the inner loop, if we encounter a node twice, we know it's been repeated.

The minimum number of pointers needed in the optimized algorithm is:

A linked list is a linear data structure.

Which of the following is an advantage of Arrays over Linked Lists?

In a doubly linked list, traversal can be preformed in ___________ directions.

The fastest method is to traverse the linked list using two pointers. This is a well known Computer Science technique: move one pointer by one node at a time, and the other pointer by two at a time.

If these pointers meet at the same node, then there's a loop. If the pointers don't meet, then the linked list doesn’t have a loop.

The intuition here is that the faster pointer will go through the entire list at least once, and will inevitably meet the slower node at the beginning again. If there is a loop, they'll eventually converge.

The pointer algorithm that moves through a sequence at two different speeds is called ___________.

Another way to think about it, notice that the distance between the two pointers increase by 1 after every iteration (one travels by 2, one travels by 1, so the distance increases). The distance is always going to be original distance + distance increase each iteration (which is 1, 2, 3, ..). Because they are moving in a fixed-length cycle, they'll eventually meet.

The space complexity of the algorithm is O(1).

The time complexity of the above algorithm is ______.

Which of the following is not a type of linked list?

In circular linked list, last node of the list points to the first node of the list.

A ______________ does not contain null pointer in any of its nodes

Asymptotic time complexity to add an element in a linked list is ___________.

One Pager Cheat Sheet

• To detect a loop in a linked list, implement a detectLoop method to take the linked list head node as the parameter and return true or false accordingly with the constraints of time and space complexities of O(n) and O(1), respectively.
• A walk is a path through a graph that can either be simple or multiple, and a cycle is a closed walk with no vertex/edge repetitions, starting and ending at the same vertex.
• A brute force solution to detect a loop in a linked list might be to manually traverse each node and check if there is any node that has a next pointer to a previous node.
• We can use a nested loop to check for cycles in a graph by keeping track of the previously-encountered vertices.
• We can solve this problem by nested traversal, which requires us to traverse each node and then re-traverse the nodes already visited in the outer loop to identify any nodes that have been repeated.
• The optimized algorithm only needs two pointers to traverse the graph, with constant space complexity, to detect any duplicate nodes.
• A Linked List is a linear data structure composed of multiple nodes, each containing data and a pointer to the next node, allowing for efficient insertion, deletion, and navigation.
• The key advantage of an array over a linked list is that it is much faster to access an element due to its contiguous block of memory, allowing random access with a calculatable memory address, contrasted with the nodes and pointers of linked lists, which requires node traversal.
• A doubly linked list provides efficient traversal both forward and backward compared to a singly linked list, which only offers forward traversal.
• By using two pointers to traverse the linked list - one slow and one fast - we can detect whether there is a loop present.
• Floyd's Cycle-Finding Algorithm is a well-known Computer Science technique used to detect if there is a loop in a linked list by moving two pointers at different speeds through the list.
• Two pointers will meet in a fixed-length cycle due to their distance increase of 1 per iteration, resulting in an O(1) space complexity.
• The algorithm has a time complexity of O(n), as it traverses the array n times to reach its end.
• Hybrid linked list is a combination of different types of linked lists to create a unique list, rather than an existing type of linked list.
• A circular linked list has a pointer from the last node to the first node, forming a loop rather than a NULL pointer.
• A circular linked list provides an infinite loop-like structure in which each node contains the address of the next node, eliminating the need for a null pointer.
• The time complexity to add an element to a linked list is O(n) due to the need to traverse the entire list to find the null pointer.