Linked List Concepts and Floyd's Algorithm

Floyd's Tortoise and Hare Algorithm

• Used for loop detection in linked lists
• Detects a loop by comparing node values
• Time complexity is O(n) for loop detection

Characteristics of Linked Lists

• A linked list with no loop has the last node pointing to NULL
• A linked list with a loop can be detected using Floyd's Tortoise and Hare algorithm

Bitonic DLL

• A Bitonic sequence is a sequence with both ascending and descending parts
• Typically sorted using the Bitonic Sort algorithm
• The merging step in the sorting process combines two sorted halves into a single sorted list
• Time complexity of sorting a Bitonic DLL using the Bitonic Sort algorithm is O(n log n)

Critical Step in Bitonic DLL

• Splitting the list into subproblems is critical for achieving the bitonic property

Segregating Even and Odd Nodes in a Linked List

• Efficient approach is iterative traversal
• Key idea is grouping nodes based on parity
• Maintaining the relative order of even and odd nodes during segregation is required for stability
• Achievable time complexity is O(n)
• Pointers are used to access neighboring nodes

Merge Sort for Doubly Linked List (DLL)

• Preferred choice for sorting a doubly linked list due to its ability to work well with linked lists
• Key step in the merge sort algorithm is merging sorted sublists
• Time complexity of the merge step is O(n log n)
• Merge sort maintains stability during sorting by maintaining the original order of equal elements
• Space complexity is O(n)

Minimum Stack

• Primary advantage is reduced space complexity compared to a regular stack