# 2 Ways to Reverse a Linked List in C++ JAVA and Python

Are you preparing for software coding interviews? Then how to Reverse a Linked List is the most common question asked by top software companies.

And today I will be showing you three ways how you can reverse a Linked List in C++, JAVA, and Python. It’s fairly easy once you know the algorithm behind it.

## Question: Reverse a Linked List – LeetCode, Interviewbit

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

### Example

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

### Example

```Input: head = [5,4]
Output: [4,5]```

### Example

```Input: head = []
Output: []```

## Solution for Reverse a Linked List

First, we will see the normal way of using a while loop to reverse the linked list. This method is also called an iterative way.

### C++ Solution

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* prev = NULL;
while(next!=NULL){
curr->next = prev;
prev = curr;
curr = next;
next = next->next;
}
curr->next = prev;
return curr;
}
};```

### Python Solution:

```# 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:
return prev```

### Recursive Method in C++:

Another way to reverse a linked list is using the Recursive Method. In this, we will pass on the head of the linked list in a function and reverse all the elements in the linked list in reverse order then add the head to the final as a node.

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
}
ListNode* node = reverseList(head -> next);
return node;
}
};```

### Recursive Solution in Python:

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def _reverse(self, node, prev=None):
if not node:
return prev
n = node.next
node.next = prev
return self._reverse(n, node)```

## Recursive Solution in JAVA

```/**
* 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 {
}
}```

## Runtime for Iterative and Recursive Solution:

Complexity analysis for Recursive Solution:

• Time complexity: O(n). Assume that n is the list’s length, the time complexity is O(n).
• Space complexity: O(n). The extra space comes from implicit stack space due to recursion. The recursion could go up to n levels deep.

Complexity analysis for Iterative Solution:

• Time complexity: O(n). Assume that n is the linked list’s length, the time complexity is O(n).
• Space complexity: O(1).