Problem Statement
Explain different types of linked lists. How would you detect a cycle in a linked list?
Explanation
A linked list is a linear data structure where elements called nodes are connected via pointers or references. Each node contains data and a reference to the next node, forming a chain-like structure.
There are several types of linked lists. A singly linked list has nodes with data and a pointer to the next node only, allowing traversal in one direction from head to tail. A doubly linked list has nodes with data and two pointers, one to the next node and one to the previous node, allowing bidirectional traversal. A circular linked list has the last node pointing back to the first node instead of null, forming a circle. This can be singly or doubly circular.
Advantages of linked lists include dynamic size that can grow or shrink at runtime, efficient insertion and deletion at O of 1 when you have a reference to the position, and no memory wastage as nodes are allocated only when needed. Disadvantages include no random access requiring O of n time to reach an element, extra memory for storing pointers in each node, and poor cache locality as nodes are scattered in memory.
To detect a cycle in a linked list, the most efficient method is Floyd's Cycle Detection Algorithm, also called the tortoise and hare algorithm. Use two pointers, slow and fast, both starting at the head. Move slow pointer one step at a time and fast pointer two steps at a time. If there is a cycle, the fast pointer will eventually meet the slow pointer inside the cycle because the fast pointer gains one step on slow pointer in each iteration. If there is no cycle, the fast pointer will reach null.
This algorithm has time complexity O of n where n is the number of nodes, and space complexity O of 1 as it uses only two pointers. Alternative methods include using a hash set to store visited nodes with O of n space, or modifying the linked list structure to mark visited nodes, but Floyd's algorithm is preferred for its constant space usage.
