LeetCode Patterns Flashcards: Linked List, Fast and Slow Pointers, Reversal, Cycle

The fast and slow pointers pattern, also called Floyd's tortoise and hare, uses two pointers moving at different speeds through a linked list. The slow pointer moves one node at a time while the fast pointer moves two nodes. If a cycle exists, the fast pointer will eventually catch the slow pointer inside the cycle. If no cycle exists, the fast pointer reaches the end. Beyond cycle detection, this pattern finds the middle of a linked list because when the fast pointer reaches the end, the slow pointer is exactly at the middle. This runs in O of n time and O of one space.

Use Floyd's cycle detection: start both slow and fast pointers at the head. Move slow one step and fast two steps at each iteration. If fast reaches a null pointer, there is no cycle. If slow and fast meet, a cycle exists. To find where the cycle begins, reset one pointer to the head and keep the other at the meeting point. Move both one step at a time. The point where they meet again is the cycle start. This works because the distance from the head to the cycle start equals the distance from the meeting point to the cycle start going around the cycle.

Use three pointers: previous initialized to null, current initialized to head, and next as a temporary variable. At each step, save current's next pointer in the temporary variable, point current's next to previous to reverse the link, move previous to current, and move current to the saved next. When current becomes null, previous points to the new head. This runs in O of n time and O of one space. Reversing a linked list is a fundamental building block used in many harder problems including reversing nodes in k-groups, palindrome linked list, and reorder list.

Use the slow and fast pointer technique. Start both at the head. Move slow one step and fast two steps. When fast reaches the end or the node before the end, slow is at the middle. For even-length lists, this gives the second of the two middle nodes. This runs in O of n time and O of one space, which is better than first counting the length and then traversing to the midpoint because it requires only one pass. Finding the middle is used as a subroutine in merge sort of linked lists and in checking if a linked list is a palindrome.

Create a dummy node as the start of the merged list and a tail pointer. Compare the heads of both lists. Attach the smaller node to tail's next, advance that list's head, and advance tail. Repeat until one list is exhausted, then attach the remaining list to tail. Return dummy's next as the merged head. This runs in O of n plus m time where n and m are the list lengths. The dummy node avoids special-casing the first element. This merge operation is the core building block for merge sort on linked lists, which achieves O of n log n sorting in O of one extra space.

Combine three patterns. First, find the middle using slow and fast pointers. Second, reverse the second half of the list starting from the middle. Third, compare nodes from the head and from the reversed second half. If all corresponding values match, it is a palindrome. Optionally, re-reverse the second half to restore the original list. This runs in O of n time and O of one space. The alternative approach of copying values to an array and using two-pointer palindrome check uses O of n space, which interviewers may ask you to optimize away. ---