Reverse a Singly Linked List (Iterative/Non-Recursive)

Given a linked list, write a program to reverse all the elements in the linked list and display the new linked list [Non-Recursive / Iterative]

Example

Input : 23 ->1 ->12 ->15 ->23 ->49 ->23
Output : 23 ->49 ->23 ->15 ->12 ->1 ->23

This is an iterative method to reverse a linked list, in this method we will change the next to previous, previous to current and cuurent to next. This can be clearly explained in the below diagram.

Implementation of Reversing a Linked List

Time Complexity : O(n)
Space Complexity : O(1)

Algorithm

1. Create three pointers (ex: temp, prev and curr), where temp is to traverse the linked list, prev to store the previous node and curr for current node

2. Till the end of the linked list,
a. Advance the temp pointer ie, temp = curr->next
b. Next becomes previous for every node ie, curr->next = prev
c. present becomes previous for the upcoming node ie, prev = curr
d. move the current to the next node ie, curr = temp

3. Make the last element as the head of the linked list ie, *head = prev

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LL{
	int data;
	LL *next;	
};


void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
	struct LL* curr=new LL;
		
		curr->data=dataToBeInserted;
		curr->next=NULL;
	
	if(*head==NULL)
			*head=curr; //if this is first node make this as head of list
		
	else
		{
			curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
			*head=curr;
		}
		
		//O(1) constant time
}

void reverseListIteratively(struct LL **head)
{
	struct LL *temp=NULL,*prev=NULL,*curr=*head; //temp for temporary head , prev to store previous node , curr for current node
	while(curr!=NULL)
	{
	    temp=curr->next; //advance the temp 
		curr->next=prev; //next becomes the previous for every node
		prev=curr; //present becomes previous for the upcoming node
		curr=temp; //move the current to next node
	}
  *head=prev;
	//O(number of nodes)
}

void display(struct LL**head)
{
	struct LL*temp=*head;
	while(temp!=NULL)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}


int main()
{
	
	struct LL *head = NULL; //initial list has no elements
	insertAtBeginning(&head,23);
	insertAtBeginning(&head,49);
	insertAtBeginning(&head,23);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,12);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);
	cout<<"Initial List is :-\n";
	display(&head);
	
	reverseListIteratively(&head);
	
	cout<<"\nAfter the reverse function the list is :- \n";
	display(&head);
	
	return 0;
}

Translate ยป