## DEV Community is a community of 704,743 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 :)

๐๐ปโโ๏ธ Tip: You need to be good at pointer manipulations.

## Explanation

We will go through every node and make it point to its preceding node. The idea is fairly simple, it's all about pointer manipulations and how you will do it. Here's the algorithm,

• Initialize three pointers, `prev = null`, `nex = null`, `cur = head`. At every iteration `cur` will point to the current node, `prev` will point to its preceding node and nex will point to its succeeding node.
• while cur โ  null i.e until we haven't reversed every node
• nex = cur ( Before we change `cur's` next, take hold of its succeeding node )
• cur โ next = prev ( Reverse the link )
• prev = cur (Update `prev` for following iteration )
• cur = nex (Update `cur` for following iteration )
• Make `head = prev` ( prev points to the first node of reversed linked list )
• return `head`

Here's a dry run on a list of 5 elements 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)
{

ListNode *prev = nullptr;
ListNode *next = nullptr;

//while cur is pointing to a node
while (cur)
{
next = cur->next;

cur->next = prev;

prev = cur;

//updating current node
cur = next;
}
//After the loop, prev will be pointed to the required node
}
``````

## Complexity Analysis

### Time Complexity: O(n)

We are traveling every node.

### Space Complexity: O(1)

We didn't use any extra space.

๐ก Can you think of a recursive solution? I will answer this in the next post.