Reverse a linked list
DSA, Easy
Which structure or algorithm, and what does it cost.
A node has val (an integer) and next (the next node, or null at the end). You get head, the first node of a singly linked list, or null for an empty list. Reverse the list by changing the next links, and return the new head. Do not create new nodes.
Examples
Input 1 -> 2 -> 3 -> null
Output 3 -> 2 -> 1 -> null
Why the links now run the other way.
Input 7 -> null
Output 7 -> null
Why one node is already reversed.
Input null
Output null
Why an empty list has nothing to reverse.
Constraints
- 0 <= number of nodes <= 5,000,000.
- Values are any integers.
- Extra memory should not grow with the list length.
Your answer must contain
- The method; code; time and extra memory; a hand trace of example 1 showing
prev,curandnextafter each step; one sentence on how a recursive version differs.