12
LinkedList Questions: Reverse a Linked List  Iterative 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 ⌛🌌
Given the head
of a singly linked list, reverse the list, and return the reversed list.
💡 Give yourself at least 1520 mins to figure out the solution :)
💁🏻♂️ Tip: You need to be good at pointer manipulations.
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 iterationcur
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 )

nex = cur ( Before we change
 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,
//Definition for singlylinked 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) {}
};
ListNode *reverseList(ListNode *head)
{
ListNode *prev = nullptr;
ListNode *cur = head;
ListNode *next = nullptr;
//while cur is pointing to a node
while (cur)
{
//get access to the node ahead
next = cur>next;
//break the forward link
cur>next = prev;
//moving prev ahead
prev = cur;
//updating current node
cur = next;
}
//After the loop, prev will be pointed to the required node
head = prev;
return head;
}
We are traveling every node.
We didn't use any extra space.
💡 Can you think of a recursive solution? I will answer this in the next post.
12