Reversing a singly linked list

Hi everybody,

I have written a code to reverse a linked list , i have done insert , display and delete now I am writing to reverse the linked list!!!
I know there two ways to do this.
1) make the head pointer point to NULL and then point the consecutive nodes point to the previous ones, and at the end make the tail node as head.
2) Swap first with last , second with second last likewise
I am applying the first method below is my code.In this if list NULL or there's only one node then it's printing the respective couts' but while list is there it's printing till cout <<"here" <<endl; , why so?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
  void link_list :: reverse_ll()
{
     // two ways 
     // 1st way :
     node * prv , *temp;
     prv = head;
     list =head;
     temp= head;
    // rest = rest->next;
     if (head ==NULL)
     {
              cout << "can not be reversed as empty list" << endl;
     }
     else 
     {
          if(head->next==NULL)
          {
            cout << "Only one node !!! result is same :) "<< endl;
          }
          else 
          {
               
               while(list!=NULL)
               {
                                cout<<"Am i here?" << endl;
               if(temp==head)
               {
                             cout <<"here" <<endl;
                 head ->next =NULL;
                 temp = list->next;
                 //rest=rest->next;
                 list=list->next;
               }
               else
               {
                    cout <<"or there?" <<endl;
                   temp ->next = prv;
                   prv = list->next;
                   temp = list->next;
                   list = list->next;
               }
               }
               head =temp;
            
          }
         
      }
 }
I tried the second also but in this console is disappearing as I am trying to reverse though same like above the empty list and the single list is getting printed.. please help!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 //2nd way
void link_list :: reverse_ll()
{
      list =head;
      node *temp;
      node *tail;
      tail =head;
      temp = new node;
      int length_ll =0;
      int i=0;
      while(list!=NULL)
      {
         list=list->next;
        length_ll++;
      }
      if(head==NULL)
      {
                    cout<<"list is empty can't reverse!!!"<<endl;
      }
      else
      {
          list=head;
      if (head->next==NULL)
      {
                           cout<<"only one node list is same!!"<<endl;
      }
      else
      {
           
      while(list->next!=tail)
      {
       for(i=0;i<length_ll;i++)
      {
         tail=tail->next;
      }
      temp = list;
      list=tail;
      tail=temp;
      list=list->next;
      length_ll--;
      }
      }
      }
      
 }
At any given time you have three consecutive nodes to look at: previous, current, and next.

You should update the current. It does point to the next, but in reverse it will point to the previous. You have to store the current->next to next before changing it. After the update you have to move forward by advancing the previous and current. The order of pointer assignments is the key.

At start the previous is a nullptr, so the head->next becomes nullptr, as is proper for the last node of the list.

At the end you have a pointer to the last node of the original list, i.e. the first node of the reversed list. Make head point to it.
Last edited on
I have applied same logic only for the first way, but it's not working
Totally untested:
1
2
3
4
5
6
7
8
9
10
11
12
13
node * prev = nullptr;
node * curr = head;
node * next;
while ( nullptr != curr ) {
  // store
  next = curr->next;
  // update
  curr->next = prev;
  // advance
  prev = curr;
  curr = next;
}
head = prev;
Thanks for the reply . but I am new to this and not aware of the term nullptr . Is it a node whose content is NULL or is it simply NULL ? I tried to google but did not get any answer.
Topic archived. No new replies allowed.