Description

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

Solution

To reverse a list, we can simply iterate through the list and move the pointers backwards. We have to have the prev node created which will eventually become the head of the list.

 1class Solution {
 2    public ListNode reverseList(ListNode head) {
 3        ListNode previous = null, current = head, next = null;
 4        while (current != null) {
 5            next = current.next;
 6            current.next = previous;
 7            previous = current;
 8            current = next;
 9        }
10        return previous;
11    }
12}
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Recursive Solution

 1class Solution {
 2    public ListNode reverseList (ListNode head) {
 3        if (head == null || head.next == null) {
 4            return head;
 5        }
 6        ListNode previous = reverseListRecursive(head.next);
 7        head.next.next = head;
 8        head.next = null;
 9        return previous;
10    }
11}
  • Time Complexity: O(n)
  • Space Complexity: O(n)