How do you find the middle of a linked list in one pass?

Explanation:
To find the middle of a linked list in one pass, you can use the two-pointer technique, often referred to as the "tortoise and hare" approach. In this method, you maintain two pointers, slow and fast. The slow pointer advances one node at a time, while the fast pointer advances two nodes at a time. By the time the fast pointer reaches the end of the list, the slow pointer will be at the middle.

Key Talking Points:

• Two-Pointer Technique: Use two pointers moving at different speeds.
• Efficiency: This method only requires one traversal of the list, which makes it O(n) in time complexity.
• Space Complexity: It uses O(1) extra space, as no additional data structures are needed.

NOTES:

Reference Table:

Pseudocode:

Here's a simple implementation in Python:

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def find_middle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Follow-Up Questions and Answers:

1. What if the linked list size is even?

   • In the case of an even number of nodes, the slow pointer will end up pointing to the second of the two middle nodes.

2. How would you modify the algorithm if you needed to find the first of the two middle nodes in an even-sized list?

   • You can modify the condition to make the fast pointer stop one node earlier. Instead of fast.next, you check fast.next.next.

3. Can you extend this to find the k-th element from the end?

   • Yes, you can extend this approach by introducing a delay for the slow pointer. Start the slow pointer k steps after the fast pointer.

4. How would this approach change if you used a doubly linked list?

   • The approach remains largely the same, as the two-pointer technique is applicable regardless of the list type. The main difference is that a doubly linked list allows backward traversal, which is not needed in this scenario.