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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL || head->next==NULL) return head;
ListNode* prev = NULL;
ListNode* curr = head;
ListNode* next = head->next;
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:
if not head or not head.next:
return head
prev = self.reverseList(head.next)
head.next.next = head
head.next = None
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.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !(head -> next)) {
return head;
}
ListNode* node = reverseList(head -> next);
head -> next -> next = head;
head -> next = NULL;
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
/**
* Definition for singly-linked list.
* 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 {
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null)
return head;
ListNode getNextNode = head.next;
ListNode createNewHead = reverseList(getNextNode);
getNextNode.next = head;
head.next = null;
return createNewHead;
}
}
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).
If you liked the answer then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.
Wanna read more interview-related questions? Check Top Interview Questions category.
