[Linked List] Loop

A linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.

Lot of questions on linked lists appears in the interviews. Interviewers in these types of questions will be more interested on how we handle pointers, how we use linked list properties etc. In this series I discuss some of the questions that appear in interviews for the linked lists.

When working with singly linked list, we are typically given a link to the first node. Common operations on a singly linked list are iterating through all the nodes, adding to the list, or deleting from the list. Algorithms for these operations generally require a well formed linked list. That is a linked list without loops or cycles in it.

If a linked list has a cycle:

• The malformed linked list has no end (no node ever has a null next pointer)
• The malformed linked list contains two links to some node
• Iterating through the malformed linked list will yield all nodes in the loop multiple times

A malformed linked list with a loop causes iteration over the list to fail because the iteration will never reach the end of the list. Therefore, it is desirable to be able to detect that a linked list is malformed before trying iteration.

The following are the questions that may arise in case of linked lists having loops:

• To detect loop in a linked list
• To calculate the node that causes loop
• To calculate length of linked list that contains loop
• To find kth node from the end of linked list that contains loop

END