Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Function signature

func ReverseList(head *ListNode) *ListNode

ListNode definition

type ListNode struct {
    Val  int
    Next *ListNode
}

Examples

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Before: 1 -> 2 -> 3 -> 4 -> 5 -> nil
After:  5 -> 4 -> 3 -> 2 -> 1 -> nil

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints

• The number of nodes in the list is in the range [0, 5000]
• -5000 <= Node.val <= 5000

Hints

1. Keep track of three pointers: previous, current, and next.
2. For each node, save its next, point it backward, then advance.
3. Return the previous pointer when current becomes nil.

Notes

• This can be solved iteratively or recursively.
• The iterative solution uses O(1) extra space.
• Be careful not to lose the reference to the rest of the list when reversing.

Follow-up

Can you solve it both iteratively and recursively?