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 as an iterative way.

/**
 * 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:

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;
    }
}
reverse a linked list

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.

Share your love

Leave a Reply