And we return 4 - which is pointing to 8. And we can simply extrapolate that to longer linked lists! Note that the recursive approach requires more space because we need to maintain our call stack.

Complexity of Final Solution

Let n be the number of nodes in the linked list. We traverse through all n nodes for O(n) linear time complexity. We reuse the old linked list nodes, so our space complexity is a constant O(1) as we do not allocate any extra space.