DEV Community is a community of 694,226 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Kathan Vakharia
DS-Algo Tenderfoot | Computer Scientist | Aspiring Gopher | DataScience Enthusiast | Python & C++ ๐

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,

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.

๐ก 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 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

//note: To make sure this works, we need to make sure:

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.