Codewhoop

# Reverse a linked list

  • To reverse a linked list we will use three pointers:

    1. p - previous : To keep track of the previous Node.
    2. c- current : To keet track of the current Node.
    3. n - next : To keep track of the next Node.

  • Initialise p to NULL and c equal to head that is it points to the first element.

  • Make n equal to the next node of the current node by equating it to link part of c pointer.

  • Remove the link between node pointed by n & node pointed by c

  • And create a backward link from the current node c to p

  • Make p = c & Move c to the next node by equating it to n.

  • Repeat these steps for every node.

  • At the end equate head pointer to p to point it to the last node.

# Source Code - C++

#include <iostream>
using namespace std;

//Creating Node Structure
struct Node{
 int data;
 Node *link;
};

Node *head=NULL;

//Function to reverse linked list
void reverseList()
{
Node *p,*c,*n;
p=NULL;
c=head;
while(c!=NULL)
{

 n=c->link;
 c->link=p;
 p=c;
 c=n;
}
head=p;
}

//Function to insert at the end of linked list
void insertEnd (int d)
{

 Node *ptr = new Node();
 ptr->data=d;
 ptr->link=NULL;

 if(head==NULL)
 head=ptr;
 else
 {
  Node *temp = head;
  while(temp->link != NULL)
  {
   temp=temp->link;
  }
  temp->link=ptr;

 }

}

//Function to display linked list
void displayList()
{
 Node *ptr=head;
 while(ptr!=NULL)
 {
  cout<<ptr->data<<" ";
  ptr=ptr->link;
 }
 cout<<"\n";
}

//Main Function
int main()
{
 insertEnd(1);
 insertEnd(2);
 insertEnd(3);
 insertEnd(4);
 insertEnd(5);

 displayList();
 reverseList();
 displayList();
 return 0;
}

Time Complexity O(n)