Describe how to implement a 'split list' operation that divides a list into two halves.

• A. Detach the head and tail.
• B. Take every other node to second list.
• C. Use slow and fast pointers to locate the middle; set end of first half's next to NULL; second half starts at middle.
• D. Divide by counting nodes and then breaking.

Answer: (C)

The idea being tested is how to split a singly linked list into two halves without counting nodes first, using a two-pointer technique to find the midpoint efficiently and then cut the list at that point.

This approach uses a slow pointer that moves one node at a time and a fast pointer that moves two nodes at a time. Start both at the head and also keep a pointer to the node just before the slow pointer. Move slow forward by one and fast forward by two in a loop. When fast reaches the end, slow will be at the start of the second half (and the node before slow is the end of the first half). Detach the first half by setting the previous node’s next to NULL, and let the second half start at slow. This yields two lists with lengths floor(n/2) and ceil(n/2): even-length lists split evenly, odd-length lists give the second half one node longer. This method runs in linear time with constant extra space, and handles edge cases like empty or single-element lists by ensuring the split creates a proper first and second half (second half may be empty in those cases).