# Solution For Reverse Linked List

The Reverse Linked List problem on LeetCode is a popular problem that involves reversing the order of a singly linked list. This problem is rated as “Easy” difficulty on the LeetCode website and is a great problem for beginners to practice with.

The problem statement is as follows:

Example:

Input: 1->2->3->4->5->NULL

Output: 5->4->3->2->1->NULL

To solve this problem, we can use the iterative or the recursive approach. However, the iterative approach is more efficient and faster.

Iterative Solution

In the iterative solution, we need to traverse the linked list from the beginning and keep reversing the pointers until we reach the end of the list. We can maintain three pointers while traversing the list – current node, previous node, and next node.

Algorithm:

1. Initialize previous node to NULL, current node to head, and next node to NULL.
2. Traverse the linked list with the help of the current node.
3. At each iteration, assign current->next = previous.
4. Move to the next node with the help of the next pointer.
5. Update previous node to the current node.
6. Continue traversing the linked list until the current node is NULL.
7. Return the new head, which is the previous node.

Code:

`ListNode* reverseList(ListNode* head) { ListNode *prev = NULL, *current = head, *next = NULL; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } return prev; }`

Time Complexity: O(n)

Space Complexity: O(1)

The above implementation takes O(n) time complexity, where n is the number of nodes in the linked list. The space complexity of the algorithm is O(1).

Recursive Solution

In the recursive solution, we reverse the list from the current node to the end of the list. Once we reach the end of the list, we update the pointer of the previous node to the current node.

Algorithm:

1. If head is NULL or the list is empty, return head.
2. Recursively reverse the rest of the list from the next node.
3. Once we reach the end of the list, update the pointer for the previous node to the current node.
4. Return the new head, which is the current node.

Code:

`ListNode* reverseList(ListNode* head) { if (head == NULL || head->next == NULL) { return head; } ListNode* newHead = reverseList(head->next); head->next->next = head; head->next = NULL; return newHead; }`

Time Complexity: O(n)

Space Complexity: O(n)

The above implementation takes O(n) time complexity, where n is the number of nodes in the linked list. The space complexity of the algorithm is O(n) because we are using recursion. Each recursive call adds a new call frame to the call stack, which takes up space. This can lead to a stack overflow error for large input sizes.

Conclusion:

In conclusion, the Reverse Linked List problem is a great practice problem for beginners to get started with linked lists. The iterative solution is more efficient and faster since it has a space complexity of O(1). However, the recursive solution is also a good implementation to understand the concept of recursion.

## Step by Step Implementation For Reverse Linked List

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {

}

// create a new node called prev and set it to null
ListNode prev = null;

// create a new node called curr and set it to head

// while curr is not null
while (curr != null) {

// create a new node called next and set it to curr.next
ListNode next = curr.next;

// set curr.next to prev
curr.next = prev;

// set prev to curr
prev = curr;

// set curr to next
curr = next;
}

// return prev
return prev;
}
}```
```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
#
# prev = None
#
# while curr is not None:
#     next = curr.next
#     curr.next = prev
#     prev = curr
#     curr = next
#
# return prev

# recursive solution

return reversed_list```
```/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {ListNode}
*/
}

// set up three pointers, prev, curr, and next
let prev = null;

// while curr is not null
while (curr) {
// set curr.next to prev
curr.next = prev;
// move prev and curr pointers forward
prev = curr;
curr = next;
// if next is not null, set next to next.next
if (next) {
next = next.next;
}
}

// return prev which is now the new head
return prev;
};```
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
//Recursive approach
return temp;
}
};```
```//Given the head of a singly linked list, reverse it in-place.

public class Solution
{
{
//edge case - if head is null, return null
{
return null;
}

//edge case - if head is the only node in the list, return head
{
}

//set up 3 pointers - prev, curr, and next
ListNode prev = null;
ListNode next = null;

//iterate through the list until curr is null
while(curr != null)
{
//set next to be curr's next node
next = curr.next;

//set curr's next node to be prev
curr.next = prev;

//move prev and curr pointers forward
prev = curr;
curr = next;
}

//set head to be prev (which is now the last node in the list)