Reverse a Linked List

EasyLinked listTwo pointers203 tests

You are given head, the first node of a singly linked list. Each node has a value val and a link next to the following node. The last node has next set to null (None in Python).

Reverse the list and return the new first node. After the change, the old last node comes first and the old first node comes last.

If the list is empty, head is null. Return null in that case.

How the input is shown

A list is written as an array of its values from first node to last node. For example, [4, 8, 15] is the list 4 -> 8 -> 15. Your function gets the first node, not the array. The judge reads your returned list back into an array.

Hint: walk the list once. Keep three names: the node before, the current node, and the node after. Point each next link backwards as you go. This takes O(n) time and O(1) extra memory.

Examples

Example 1

Input:: [4,8,15,16]
Output:: [16,15,8,4]

The list 4 -> 8 -> 15 -> 16 becomes 16 -> 15 -> 8 -> 4. The node with 16 is the new first node.

Example 2

Input:: [-3,7]
Output:: [7,-3]

With two nodes, the second node now points to the first, and the first node now points to null.

Example 3

Input:: []
Output:: []

The list is empty, so head is null and the answer is also null (an empty list).

Constraints

The list has 0 to 50 nodes.
-100 <= val <= 100

Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.