An Interest In:
Web News this Week
- April 18, 2024
- April 17, 2024
- April 16, 2024
- April 15, 2024
- April 14, 2024
- April 13, 2024
- April 12, 2024
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 Analysis
The Question
Given thehead
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( curnext
) 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:
Original Link: https://dev.to/kathanvakharia/likedlist-questions-reverse-a-linked-list-recursive-version-ige
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To