Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Constraints:
The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000
My Solution
We first iterate through the Linked List and store all the values in an ArrayList. We then go back to the head of the list and copy the values from the ArrayList in reverse order.
Time complexity would be O(n), where n is the number of nodes in the list because we do two passes through it. Space complexity would be O(n) for the space required for the ArrayList.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
List<Integer> arr = new ArrayList<>();
ListNode n = head;
while (n != null) {
arr.add(n.val);
n = n.next;
}
n = head;
for (int i = arr.size()-1; i >= 0; i--) {
n.val = arr.get(i);
n = n.next;
}
return head;
}
}