Reverse a Singly Linked List in C++.

Given the head of the singly linked list, reverse the given linked list and return it.

Example 1: 
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Example 2:
Input: 1->0->4->7->2->3->NULL
Output: 3->2->7->4->0->1->NULL

Approach 1: Using Three Pointer.

In this approach, you need a three-pointer previous(prev), current(curr), and next(nxt) to keep track of nodes.

Initialize three-pointers, prev as NULL, curr as head of the linked list and next as NULL.

Iterate through the linked list and follow below four steps to reverse the linked list:

next = curr->next;
curr->next = prev;
prev = curr;
curr = next;

C++ Solution code:

/*C++ Program to reverse a linked list*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//function to reverse linked list
ListNode *reverseList(ListNode *head){

    ListNode *curr = head;
    ListNode *prev = NULL, *next = NULL;

    while(curr != NULL){
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
    return head;
}
//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
int main(){
    ListNode *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);

    cout<<"Linked List before reverse: ";
    printList(head);

    ListNode *newHead = reverseList(head);

    cout<<"\nLinked List after reverse: ";
    printList(newHead);
    return 0;
}

Output:

Linked List before reverse: 1 2 3 4 5
Linked List after reverse: 5 4 3 2 1

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

Approach 2: Using Recursion.

This is a baisc recurison in which one base is when head is NULL or head->next is NULL. It means our list contain no node or it contain only one node and we cannot reverse a single node.

C++ Solution Code:

/*C++ Program to reverse a linked list using recursion*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//function to reverse linked list
ListNode *reverseList(ListNode *head){

    //base case
    if(head == NULL || head->next == NULL)
       return head;

    ListNode *newHead = reverseList(head->next);
    head->next->next = head;

    head->next = NULL;

    return newHead;
}
//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
int main(){
    ListNode *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);

    cout<<"Linked List before reverse: ";
    printList(head);

    ListNode *newHead = reverseList(head);

    cout<<"\nLinked List after reverse: ";
    printList(newHead);
    return 0;
}

Output:

Linked List before reverse: 1 2 3 4 5
Linked List after reverse: 5 4 3 2 1

Time Complexity: O(n)
Space Complexity: O(n) stack space

Related Articles:

Convert Binary Linked List to Integer.

Find the Middle of the Singly Linked List in C++.

Merge Two Sorted Linked List in C++.

Intersection Point of Two Linked Lists in C++.

Detect Cycle in a Linked List in C++.

Reverse a Singly Linked List in C++.

No comments:

Post a Comment