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

Example 1:

Question:

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

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution:

• Maintain three variables (pointers): prev, curr and next.
• At each step of the loop: you need to
  • Make the next of curr equal to the prev
  • Make prev equal to curr and curr equal to the next.
  • If curr becomes null at any point (we don't need the next step), and hence break out of the while loop.
  • Make next equal to curr.next

Code:

class Solution {
    public ListNode reverseList(ListNode head) {

        if(head == null) return null;

        ListNode prev = null, curr = head, next = curr.next;

        while(curr != null){

            curr.next = prev;
            prev = curr;
            curr = next;

            if(curr == null) break;
            else next = curr.next;

        }

        return prev;

    }
}

Complexity:

• Time: O(N)
• Space: O(1)