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.