How would you traverse a Linked List in O(n1/2)?

Traversal more efficient than O(n) is not possible, since “traversal” requires accessing each node in turn.

It is possible to make random access faster than O(n) though, by maintaining a second linked list that retains links to intermediate nodes; insertion, deletion, and appending cost will go up though, due to the increased complexity of maintenance of the second list.