LikedList Questions: Reverse a Linked List – Recursive version

In this series of posts, I will discuss coding questions on the LinkedList Data structure.
The posts in this series will be organized in the following way,

Question Link ❓
Possible Explanation ?
Documented C++ Code ?
Time and Space Complexity Analysi…


This content originally appeared on DEV Community and was authored by Kathan Vakharia

In this series of posts, I will discuss coding questions on the LinkedList Data structure.
The posts in this series will be organized in the following way,

  1. Question Link ❓
  2. Possible Explanation ?
  3. Documented C++ Code ?
  4. Time and Space Complexity Analysis ⌛?

The Question

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

https://leetcode.com/problems/reverse-linked-list/

? Give yourself at least 15-20 mins to figure out the solution :)

Explanation

Its bit tricky so pay your atmost attention,

The idea is to make current node's successor( cur→next ) point to current and there by reversing the list. (Here, we are under assumption that the list after current node is already reversed ).

Lastly, we will return the last node's pointer as the new head of our reversed linkedlist.

See the recursion animation to make things more clear,

C++ Code

Definition of Linked List

//Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

Solution

ListNode *reverseList(ListNode *head)
    {
        /*
        *Approach
            -Let's say list is n0 -> n1 ->... "nk" -> nk+1 -> ...n->null
            -when we are on nk, we assume nk+1 <-...n i.e. the list ahead is reversed 
        */

       //* When 1. list contains 0 or 1 node, 
       //* 2. head is pointing last node
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode *last = reverseList(head->next);

        //note: To make sure this works, we need to make sure:
        //> head->next and head exits (base condition)
        head->next->next = head; //! crux

        head->next = nullptr;

        return last;
    }

Complexity Analysis

Time Complexity: O(n)

We will visit every node once.

Space Complexity: O(n)

The size of recursion stack as we will go n levels deep.

References:

https://leetcode.com/problems/reverse-linked-list/solution/


This content originally appeared on DEV Community and was authored by Kathan Vakharia


Print Share Comment Cite Upload Translate Updates
APA

Kathan Vakharia | Sciencx (2021-07-10T05:51:03+00:00) LikedList Questions: Reverse a Linked List – Recursive version. Retrieved from https://www.scien.cx/2021/07/10/likedlist-questions-reverse-a-linked-list-recursive-version/

MLA
" » LikedList Questions: Reverse a Linked List – Recursive version." Kathan Vakharia | Sciencx - Saturday July 10, 2021, https://www.scien.cx/2021/07/10/likedlist-questions-reverse-a-linked-list-recursive-version/
HARVARD
Kathan Vakharia | Sciencx Saturday July 10, 2021 » LikedList Questions: Reverse a Linked List – Recursive version., viewed ,<https://www.scien.cx/2021/07/10/likedlist-questions-reverse-a-linked-list-recursive-version/>
VANCOUVER
Kathan Vakharia | Sciencx - » LikedList Questions: Reverse a Linked List – Recursive version. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/07/10/likedlist-questions-reverse-a-linked-list-recursive-version/
CHICAGO
" » LikedList Questions: Reverse a Linked List – Recursive version." Kathan Vakharia | Sciencx - Accessed . https://www.scien.cx/2021/07/10/likedlist-questions-reverse-a-linked-list-recursive-version/
IEEE
" » LikedList Questions: Reverse a Linked List – Recursive version." Kathan Vakharia | Sciencx [Online]. Available: https://www.scien.cx/2021/07/10/likedlist-questions-reverse-a-linked-list-recursive-version/. [Accessed: ]
rf:citation
» LikedList Questions: Reverse a Linked List – Recursive version | Kathan Vakharia | Sciencx | https://www.scien.cx/2021/07/10/likedlist-questions-reverse-a-linked-list-recursive-version/ |

Please log in to upload a file.




There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.