linked list all cpp

linkedlist.cpp

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

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

void insertAtTheBegining(Node * &head, int el) {
    Node * temp = new Node;
    temp->data = el;
    temp -> next = NULL;
    if(head ==  NULL){
        head = temp;
        return;
    }
    temp->next = head;
    head = temp;
    return;
}

void insertAtTheEnd(Node * &head, int el){
    Node *ptr = new Node;
    ptr -> data = el;
    ptr -> next = NULL;
    if(head == NULL){
        head = ptr;
        return;
    }
    Node * it = head;
    while(it -> next != NULL){
        it = it -> next;
    }
    it -> next = ptr;
    return;
}

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

void reversePrint(Node *head) {
    if(head == NULL) {
        return;
    }
    reversePrint(head->next);
    cout << head->data << " ";
    return;
}

void deleteFromEnd(Node * & head) {
    if (head == NULL) {
        return;
    }
    if (head->next == NULL) {
        delete head;
        head = 0;
        return;
    }
    Node *it = head;
    while (it->next->next != NULL) {
        it = it->next;
    }
    delete it->next;
    it->next = 0;
    return;
}

void deleteFromHead(Node * &head){
    if(head == NULL){
        return;
    }
    if(head -> next == NULL){
        delete(head);
        head = NULL;
        return;
    }
    Node * temp = head;
    head = head -> next;
    temp -> next = NULL;
    delete(temp);
    return;
}

void findElementAtK(Node * head, int k){
    Node * it = head;
    int i = k - 1;
    while(it && i){
        i--;
        it = it -> next;
    }

    if(!it){
        cout << "Position Entered was Invalid, Please enter a valid Position!\n";
        return;
    }
    cout << "Element at kth Position is : " << (it -> data) << '\n';
    return;
}

void findMidOfTheList(Node * head){
    Node * it1, * it2;
    it1 = it2 = head;
    /// it2 != NULL is for the Even length list case and it->next != NULL is for the odd length list case.
    while(it2 && it2 -> next){
        it1 = it1 -> next;
        it2 = it2 -> next -> next;
    }
    cout << "Middle Element of the Linked List is : " << (it1 -> data) <<'\n';
    return;
}

int LengthOfLinkedList(Node * head){
    int l=0;
    Node *it = head;
    while(it){
        l++;
        it = it -> next;
    }
    return l;
}

/// Given two sorted Linked list merge them into One.
Node * MergeSorted(Node * head1, Node * head2){
    Node * it1 = head1, *it2 = head2, *sortHead = NULL, *sortTail;
    while(it1 && it2){
        if((it1->data) < (it2->data)){
            if(sortHead == NULL){
                sortHead = sortTail =it1;
                it1 = it1 -> next;
            } else {
                sortTail -> next = it1;
                it1 = it1 -> next;
                sortTail = sortTail -> next;
            }
            sortTail -> next = NULL;
        } else {
            if(sortHead == NULL){
                sortHead = it2;
                it2 = it2 -> next;
                sortTail = sortHead;
            } else {
                sortTail -> next = it2;
                it2 = it2 -> next;
                sortTail = sortTail -> next;
            }
            sortTail -> next = NULL;
        }
    }
    while(it1){
        sortTail -> next = it1;
        it1 = it1 -> next;
        sortTail = sortTail -> next;
        sortTail -> next = NULL;
    }
    while(it2){
        sortTail -> next = it2;
        it2 = it2 -> next;
        sortTail = sortTail -> next;
        sortTail -> next = NULL;
    }
    return sortHead;
}

/// Eliminate Duplicates from a sorted LinkedList.
void EliminateDuplicates(Node * head){
    Node * it = head;
    /// check condition.
    while(it && it->next){
        if((it->data) == (it->next->data)){
            Node * temp = it -> next;
            it -> next = it -> next -> next;
            temp -> next = NULL;
            delete (temp);
        } else {
            it = it -> next;
        }
    }
}

/// Check Palindrome, Approach - Returning a Structure with a Node address and a boolean value.

struct myvar{
    Node *add;
    bool check;
};

myvar checkPalindrome(Node *head, Node*curr){
    myvar var;
    if(curr -> next == NULL){
        if(curr -> data == head->data){
            var.add = head -> next;
            var.check = true;
        } else {
            var.add = NULL;
            var.check = false;
        }
        return var;
    }

    myvar subans = checkPalindrome(head, curr -> next);
    if(subans.check == false){
        return subans;
    }

    if(subans.add -> data != curr -> data){
        subans.add = NULL;
        subans.check = false;
        return subans;
    }
    subans.add = subans.add -> next;
    subans.check = true;
    return subans;
}

/// Check if two linked list are reverse of each other.
myvar checkIfReverse(Node * head1, Node * head2){
    myvar var;
    if(head2 -> next == NULL){
        if(head2->data == head1->data){
            var.add = head1 -> next;
            var.check = true;
        } else {
            var.add = NULL;
            var.check = false;
        }
        return var;
    }
    myvar subans = checkIfReverse(head1, head2->next);
    if(subans.check == false){
        return subans;
    }
    if(subans.add->data != head2->data){
        subans.add = NULL;
        subans.check  = false;
        return subans;
    }
    subans.add = subans.add->next;
    subans.check = true;
    return subans;
}

/// Append last n element to the front of the linked list.
void AppendLastN(Node * &head, int n){
    Node *it = head;
    int l = LengthOfLinkedList(head);
    if(l-n == 0){
        return;
    }
    if(l-n < 0){
        cout << "Operation Not Possible!";
        return;
    }
    l = l - n - 1;
    while(l){
        it = it -> next;
        l--;
    }
    Node * newHead = it -> next;
    it -> next = NULL;
    it = newHead;
    while(it -> next != NULL){
        it = it -> next;
    }
    it -> next = head;
    head = newHead;
}

void deleteElementAtKPosition(Node * &head, int k){
    if(k == 1){
        deleteFromHead(head);
        return;
    }
    int l = LengthOfLinkedList(head);
    if(k > l){
        cout << "Deletion not Possible! Value of k does not exist!";
        return;
    }
    Node * temp, *it = head;
    k = k - 2;
    while(k){
        it = it -> next;
        k--;
    }
    temp = it -> next;
    it -> next = it -> next -> next;
    temp -> next = NULL;
    delete (temp);
}

void insertElementAtKPosition(Node * &head, int k, int el){
    if(k == 1){
        insertAtTheBegining(head, el);
        return;
    }
    int l = LengthOfLinkedList(head);
    if(k > l+1){
        cout << "Insertion Not Possible! Invalid Value of k!";
        return;
    }
    Node * ptr = new Node, *it = head;
    ptr -> data = el;
    ptr -> next = NULL;
    k = k - 2;
    while(k){
        k--;
        it = it -> next;
    }
    ptr -> next = it -> next;
    it -> next = ptr;
    return;
}

void SwapNodesIandJ(Node * &head, int i, int j){
    if(i == j){
        return;
    }
    int k = min(i, j);
    j = max(i, j);
    i = k;
    Node * previ = NULL, *prevj = NULL, *curri = head, *currj = head;
    k = i - 1;
    while(k--){
        previ = curri;
        curri = curri -> next;
    }

    k = j - 1;
    while(k--){
        prevj = currj;
        currj = currj -> next;
    }

    if(curri == NULL || currj == NULL){
        cout << "Either of the index is invalid!";
        return;
    }

    if(previ != NULL){
        previ -> next = currj;
    } else {
        head = currj;
    }

    if(prevj != NULL){
        prevj -> next = curri;
    } else {
        head = curri;
    }

    Node * temp = currj -> next;
    currj -> next = curri -> next;
    curri -> next = temp;
}

/// We can check anagram by using a counter for all the values as done below OR by sorting using merge sort with O(n log(n)).
bool checkAnagram(Node *head1, Node *head2){
    map<int, int> m1, m2;
    Node * it1 = head1, * it2 = head2 ;
    while(it1 && it2){
        m1[it1 -> data]++;
        m2[it2 -> data]++;
        it1 = it1 -> next;
        it2 = it2 -> next;
    }
    if(it1 == NULL && it2 != NULL || it2 == NULL && it1 != NULL){
        m1.clear();
        m2.clear();
        return false;
    }
    if(m1.size() != m2.size()){
        return false;
    }
    map<int, int> :: iterator i, j;
    i = m1.begin(), j = m2.begin();
    for( ; i!= m1.end() && j!=m2.end() ; i++, j++){
        if(i->first != j->first){
            return false;
        } else {
            if(i->second != j->second){
                return false;
            }
        }
    }
    return true;
}

/// Rearranging Linked List in such a way that all the even nodes are after all the odd nodes.
/// Method : 1 - By reaching the end of the list by one pointer the traversing again and pushing all even nodes at back.
/// Method : 2 - By Separating the even and the odd Nodes, and finally joining them.
/// Both these method work in O(n), with O(1) extra space.

void separateOddEven(Node * &head){
    Node *oddHead = NULL, * evenHead = NULL, *oddTail = NULL, * evenTail = NULL;
    Node * it  = head;
    while(it){
        if((it-> data) % 2 == 0){
            if(evenHead == NULL){
                evenHead = evenTail = it;
                it = it -> next;
                evenTail -> next = NULL;
            } else {
                evenTail -> next = it;
                evenTail = it;
                it = it -> next;
                evenTail -> next = NULL;
            }
        } else {
            if(oddHead == NULL){
                oddHead = oddTail = it;
                it = it -> next;
                oddTail -> next = NULL;
            } else {
                oddTail -> next = it;
                oddTail = it;
                it = it -> next;
                oddTail -> next = NULL;
            }
        }
    }
    it = oddHead;
    while(it->next){
        it = it -> next;
    }
    it -> next = evenHead;
    head = oddHead;
    oddHead = oddTail = evenTail = evenHead = NULL;
}

/// **** SORTINGS IN LINKED LIST **** ///

/// Selection Sorting.
Node * RemoveSmallestAndReturn(Node * &head){
    if(head == NULL){
        return NULL;
    }
    Node *it = head, *prevofsmallest = NULL, *smallest = NULL, *prevofIt = NULL;
    int min = INT_MAX;
    while(it){
        if(it -> data < min){
            min = it -> data;
            prevofsmallest = prevofIt;
            smallest = it;
        }
        prevofIt = it;
        it = it -> next;
    }
    if(prevofsmallest == NULL){
        head = head -> next;
    } else {
        prevofsmallest -> next = smallest -> next;
    }
    smallest -> next = NULL;
    return smallest;
}

void selectionSort(Node * &head){
    if(head == NULL){
        return;
    }
    Node *newHead = NULL, *newTail = NULL, * smallest;
    do {
        smallest = RemoveSmallestAndReturn(head);
        if(newHead == NULL){
            newHead = newTail = smallest;
        } else {
            newTail -> next = smallest;
            newTail = smallest;
        }
    } while(smallest != NULL);
    head = newHead;
    newHead = newTail = NULL;
}

/// Bubble Sorting.
/// we are swapping the data in the nodes we can also do it by swapping the nodes.
void BubbleSort(Node * head){
    if(head == NULL){
        return;
    }
    int n = LengthOfLinkedList(head);
    if(n == 1){
        return;
    }
    for(int i=1 ; i<=n ; i++){
        Node * j1 = head, *j2 = head -> next;
        for(int j=1 ; j<= n-i ; j++){
            if(j1 -> data > j2 -> data){
                int temp = j1 -> data;
                j1-> data = j2 -> data;
                j2 -> data = temp;
            }
            j1 = j2;
            j2 = j2 -> next;
        }
    }
    return;
}

/// Insertion Sort.
void InsertionSort(Node * head){
    Node * it, * curr;
    curr = head -> next;
    while(curr){
        for(it = head ; it != curr ; it = it -> next){
            if(it -> data > curr -> data){
                int temp = it -> data;
                it -> data = curr -> data;
                curr -> data = temp;
            }
        }
        curr = curr -> next;
    }
}

/// Merge Sort.

/// It uses Function MergeSorted.
Node * ReturnPrevOfMid(Node * head){
    Node * it1 = head, * it2 = head, *prevofMID = NULL;
    while(it2 && it2 -> next){
        prevofMID = it1;
        it1 = it1 -> next;
        it2 = it2 -> next -> next;
    }
    return prevofMID;
}

void MergeSort(Node * &head){
    if(head == NULL || head -> next == NULL){
        return;
    }
    Node * mid = ReturnPrevOfMid(head), * head1, * head2;
    head1 = head;
    head2 = mid -> next;
    mid -> next = NULL;
    MergeSort(head1);
    MergeSort(head2);
    head = MergeSorted(head1, head2);
}

/// Reverse a LinkedList Iterative.
void reverseALinkedListIterative(Node * & head){
    Node * prev = NULL, * curr = head, * next = NULL;
    while(curr){
        next = curr -> next;
        curr -> next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
}

/// Reverse a linked list Recursive.
/* The Implementation below is Tail recursive We can also do it by Normal Recursion Method */
Node * reverseALinkedListRecursiveHelper(Node * prev, Node * curr, Node * next){
    if(curr == NULL){
        return prev;
    }
    next = curr -> next;
    curr -> next = prev;
    prev = curr;
    curr = next;
    return reverseALinkedListRecursiveHelper(prev, curr, next);
}

void reverseALinkedListRecursive(Node * &head){
    if(head == NULL){
        return ;
    }
    head = reverseALinkedListRecursiveHelper(NULL, head, head -> next);
}

/// K reverse in a linked List.

Node * KReverseALinkedListHelper(Node * head, int k){
    Node * prev = NULL, * curr = head, * next = head -> next;
    int i=k;
    while(curr && i--){
        next = curr -> next;
        curr -> next = prev;
        prev = curr;
        curr = next;
    }

    if(curr != NULL){
        head -> next = KReverseALinkedListHelper(next, k);
    }
    return prev;
}

void KReverseALinkedList(Node * &head, int k){
    if(head == NULL){
        return;
    }
    int l = LengthOfLinkedList(head);
    if(l < k){
        cout << "Value of the K entered is greater than K, Enter a Valid Value of K";
        return;
    }
    head = KReverseALinkedListHelper(head, k);
    return;
}

int main(){
    Node * head1 = NULL, *head2 = NULL;
    return 0;
}