Day 10: 100 Days of DSA

Welcome to the day 10 of 100 days of DSA challenge. Today I’ll be solving five problems on linked lists. Linked Lists are an important data structure and they are known for their dynamic and non contigous memory allocation. Let’s see what these five problems are.

Today’s questions mainly focus on the fast and slow pointer techniques to solve questions in linked list. The fast and slow pointer technique in a linked list involves using two pointers to traverse the list at different speeds. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. This approach is useful for detecting cycles, finding the middle element, or performing other optimizations, as the fast pointer can quickly "catch up" with the slow pointer under certain conditions.

1. Implement a singly linked list with operations for insertion, deletion, and traversal.

Code:

// To implement insertion, deletion, and traversal on a singly linked list

#include<iostream>
using namespace std;

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

        Node(int data){
            this->data=data;
            this->next=NULL;
        }

        void deleteNode(Node* head, int data){
            Node* temp=head;
            while(temp->next->data!=data){
                temp=temp->next;
            }
            Node* toDelete=temp->next;
            temp->next=temp->next->next;
            delete toDelete;
        }

        void display(Node* head){
            Node* temp=head;
            while(temp!=NULL){
                cout<<temp->data<<" ";
                temp=temp->next;

            }
            cout<<endl;
        }        
};

int main(){
    cout<<"Inserting five node in the linked list:"<<endl;
    Node* head=new Node(10);
    head->next=new Node(20);
    head->next->next=new Node(30);
    head->next->next->next=new Node(40);
    head->next->next->next->next=new Node(50);
    head->display(head);
    cout<<"Deleting node with data 30:"<<endl;
    head->deleteNode(head, 30);
    cout<<"Linked list after deletion:"<<endl;
    head->display(head);


}

Output:

2. Write a program to reverse a linked list.

Code:

// To reverse a linked list

#include<iostream>
using namespace std;

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

    Node(int data){
        this->data=data;
        this->next=NULL;
    }
};

Node* reverseLinkedList(Node* head){
    Node* Prev=NULL;
    Node* Curr=head;
    Node* Next=NULL;

    while(Curr!=NULL){
        Next=Curr->next;
        Curr->next=Prev;
        Prev=Curr;
        Curr=Next;
    }

    return Prev;
}

void display(Node* head){
    while(head!=NULL){
        cout<<head->data<<"->";
        head=head->next;
    }
    cout<<"NULL"<<endl;
}

int main(){
    Node* head=new Node(10);
    head->next=new Node(20);
    head->next->next=new Node(30);
    head->next->next->next=new Node(40);
    head->next->next->next->next=new Node(50);
    cout<<"Original Linked List:"<<endl;
    display(head);
    Node* rev=reverseLinkedList(head);
    cout<<"After reversing linked list:"<<endl;
    display(rev);
}

Output:

3. Solve the "detect a cycle in a linked list" problem using Floyd’s Cycle Detection algorithm.

Code:

// To find a cycle in the linked list

#include<iostream>
using namespace std;
class Node{
    public:
      int data;
      Node* next;

      Node(int data){
        this->data=data;
        this->next=NULL;
      }
};

bool cycleDetection(Node* head){
    if(head == NULL || head->next==NULL){
        return false;
    }

    Node* slow=head;
    Node* fast=head;
    while(fast!=NULL && fast->next!=NULL){
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast){
            return true;
        }
    }
    return false;
}

int main(){
    Node* head = new Node(10);
    head->next = new Node(20);
    head->next->next = new Node(30);
    head->next->next->next = new Node(40);
    head->next->next->next->next = new Node(50);
    head->next->next->next->next->next = head->next;
    bool res=cycleDetection(head);
    if(res){
        cout<<"Yes the linked list has a cycle"<<endl;
    }
    else{
        cout<<"No cycle detected";
    }


}

Output:

4. Write a program to merge two sorted linked lists.

Code:

// To merge two sorted linked lists
#include<iostream>
using namespace std;
class Node{
    public:
      int data;
      Node* next;

      Node(int data){
        this->data=data;
        this->next=NULL;
      }
};

Node* mergeSorted(Node* head1, Node* head2){
    Node* temp1=head1;
    Node* temp2=head2;
    Node dummy1(0);
    Node* dummy= &dummy1;

    while(temp1!=NULL && temp2!=NULL){
        if(temp1->data<=temp2->data){
            dummy->next=temp1;
            temp1=temp1->next;
        }
        else{
            dummy->next=temp2;
            temp2=temp2->next;
        }
        dummy=dummy->next;

    }
    return dummy1.next;
}

void display(Node* head){
    while(head!=NULL){
        cout<<head->data<<"->";
        head=head->next;
    }
    cout<<"NULL"<<endl;
}

int main(){
    cout<<"First linked list:"<<endl;
    Node* head1=new Node(10);
    head1->next=new Node(30);
    head1->next->next=new Node(50);
    display(head1);

    cout<<"Second linked list:"<<endl;
    Node* head2=new Node(20);
    head2->next=new Node(40);
    head2->next->next=new Node(60);
    display(head2);

    cout<<"Merging the two we get:"<<endl;
    Node* res=mergeSorted(head1,head2);
    display(res);
}

Output:

5. Solve the "find the middle element of a linked list" problem.

Code:

// To find the middle element in a singly linked list.

#include<iostream>
using namespace std;
class Node{
    public:
      int data;
      Node* next;

      Node(int data){
        this->data=data;
        this->next=NULL;
      }

      void findMiddleElement(Node* head){
        Node* slow=head;
        Node* fast= head->next->next;

        while(fast!=NULL && fast->next!=NULL){
            fast=fast->next->next;
            slow=slow->next;
        }

        cout<<slow->data<<endl;
      }
};

int main(){
    Node* head=new Node(10);
    head->next=new Node(20);
    head->next->next=new Node(30);
    head->next->next->next=new Node(40);
    head->next->next->next->next=new Node(50);
    head->next->next->next->next->next=new Node(60);
    cout<<"The middle element is:";
    head->findMiddleElement(head);

}

Output:

This is all for today! Happy Coding ✨🍀