This is one of the most important interview question, How to reverse a linked list using iterative and recursive approach? In this article, I will help you to understand, how to approach and solve this problem. I’m going to make a diagrammatic representations, so that you can easily understand the problem well.

Here is our given problem, Reverse a singly linked list.

Example:

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

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Diagrammatic explanations for Iterative Approach

Diagrammatic explanations for Recursive Approach

Solution:

public ListNode reverseList(ListNode head) {
    /* iterative solution */
    ListNode newHead = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = newHead;
        newHead = head;
        head = next;
    }
    return newHead;
}

public ListNode reverseList(ListNode head) {
    /* recursive solution */
    return reverseListInt(head, null);
}

private ListNode reverseListInt(ListNode head, ListNode newHead) {
    if (head == null)
        return newHead;
    ListNode next = head.next;
    head.next = newHead;
    return reverseListInt(next, head);
}

Time Complexity: O(n)

Space Complexity: O(n) Since we constructing newHead to return.

Note:

If you like this article, please subscribe my blog by entering your email id. So that, you won’t miss any new posts from me. I made a progress to solve algorithm problems daily with detailed and diagrammatic explanations, so others can easily understand the solution. Still now, I solved daily and made blogs with detailed explanations. If you like to support my work, please subscribe my blog via email. Kindly ignore, if you are already subscribed😊

One thought on “7) Reverse a Linked List – Iterative and Recursive approach

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s