Reverse Linked List: 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 the nodes in the list is in the range [0, 5000].
• -5000 <= Node.val <= 5000

Try this Problem on your own or check similar problems:

1. Palindrome Linked List
2. Reverse Linked List II
3. Remove Nodes From Linked List

Solution:

public ListNode reverseList(ListNode head) {
    if(head == null || head.next == null) return head;

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

    while(next != null){
        curr = next;
        next = next.next;
        curr.next = prev;
        prev = curr;
    }

    return prev;
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Explanation:

We first check if the list is empty or only contains one element and we return the head of the list as it is. In this solution we have three pointers prev, next, curr. You can think of curr as the current node we’re dealing with, prev the node before it, and next as our iterator through the list. We move next until we reach the end of the list, but before that we pick the current node. This is an in-place list reordering, in other words you can think of nodes as static not moving, the only thing changing is the direction of relation arrow between curr and prev (from ->, to <-). At the end of the iteration curr and prev will point to the last element in the original list and our new list head. Since we traverse the list only once we have linear time complexity O(n), and we don’t create any additional data structure leading to constant space complexity. For the ones interested in recursive solution here is the short solution using recursion:

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        return helper(head, null);
    }
    private ListNode helper(ListNode head, ListNode newHead){
        if(head == null){
            return newHead;
        }
        ListNode next = head.next;
        head.next = newHead;
        return helper(next, head);
    }
}