sp-linked-list

https://practice.geeksforgeeks.org/tracks/sp-linked-list/?batchId=152

Problems

Print Linked List elements Solved on: April 20, 2020

C++

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

Linked List Insertion Solved on: April 20, 2020

C++

// function inserts the data in front of the list
Node *insertAtBegining(Node *head, int newData) {
   
   struct Node *temp=new Node(newData);
   if (head == NULL) {
       head = temp;
   } else {
       temp->next = head;
       head = temp;
   }
   return head;
}


// function appends the data at the end of the list
Node *insertAtEnd(Node *head, int newData)  {
   
   struct Node *newNode =new Node(newData);
   Node *temp=head;
   
   if (head == NULL) {
       head = newNode;
   } else {
       while (temp->next !=NULL) {
           temp=temp->next;
       }
       temp->next = newNode;
   }
   return head;

}

Delete a Node in Single Linked List Solved on: April 20, 2020

C++

/*You are required to complete below method*/
Node* deleteNode(Node *head,int x)
{
    int c=1;
    Node *temp1 = head;
    
    if (x==1) {
        head = temp1->next;
    } else {
        while (c<x-1) {
            temp1 = temp1->next;
            c++;
        }
        temp1->next = temp1->next->next;        
    }

    return head;
}

Count nodes of linked list Solved on: April 20, 2020

C++

// head : reference to head of linked list
int getCount(struct Node* head){
    int c=0;
    while (head != NULL) {
        head = head->next;
        c++;
    }
    return c;
}

Node at a given index in linked list Solved on: April 20, 2020

C++

// Should return data of node at given index. The function may
//  assume that there are at least index+1 nodes in linked list
int GetNth(struct node* head, int index){
  int c=1;
  node *temp = head;
  while (c!=index) {
      temp = temp->next;
      c++;
  }
  return temp->data;
}

Finding middle element in a linked list Solved on: April 20, 2020

C++

int getMiddle(Node *head)
{
    int c=0,mid=0;
    Node *temp=head;
    while (temp!=NULL){
        temp=temp->next;
        c++;
    }

    mid = int(c/2)+1;
    Node *temp1=head;
    int i=0;
    while (i<mid-1) {
        temp1 = temp1->next;
        i++;
    }
    return temp1->data;
}

Reverse a linked list Solved on: 21st April 2020

C++

Node* reverseList(Node *head) {
    Node *prev = NULL;
    Node *curr = head;
    Node *next = NULL;

    while (curr != NULL) {
        next = curr->next;
        curr -> next = prev;
        prev = curr;
        curr = next;
    }    
    head = prev;
    return head;
}

Detect Loop in linked list Solved on: 21st April 2020

C++

int detectloop(Node *head) {

    Node *temp1 = head;
    Node *temp2 = head;
    while (temp1 != NULL && temp2 != NULL  && temp2->next != NULL) {
        temp1 = temp1->next;
        temp2 = temp2->next->next;
        if (temp1 == temp2) {
            return 1;
        }
    }
    return 0;
}

Remove loop in Linked List Solved on: 21st April 2020

C++

void removeTheLoop(Node *head)
{
    Node *temp1 = head;
    Node *temp2 = head;
    
    while (temp1 && temp2 && temp2->next != NULL) {
        temp1 = temp1-> next;
        temp2 = temp2->next->next;
        if (temp1 == temp2) {
            temp1=head;
            while(temp1->next != temp2->next)
            {
                temp1=temp1->next;
                temp2=temp2->next;
            }
            temp2->next=NULL;
        }
    }
}

Rotate a Linked List Solved on: 21st April 2020

C++

Node* rotate(Node* head, int k) {
    Node *temp1 = head;
    while (temp1->next) {
        temp1= temp1->next;
    }
    temp1->next = head;
    
    int c=1;
    Node *temp2 = head;
    while (c<k && temp2->next) {
        temp2 = temp2->next;
        c++;
    }
    head = temp2->next;
    temp2->next = NULL;
    return head;
}

Delete node in Doubly Linked List Solved on: 23rd April 2020

C++

void deleteNode(Node **head_ref, int x)
{  
    int c=1;
    
    Node *temp = *head_ref;
    
    if (*head_ref == NULL)  
        return;  
    
    // If x is head node
    if(x==1){
        *head_ref = temp->next;
        temp->next->prev = NULL;
        return;
    }
    else {
        while (c<x-1 && temp->next) {
            temp = temp->next;
            c++;
        }
        Node *temp1 = temp;
        // If the x is not a last node
        if (temp->next->next){
            temp->next = temp->next->next;
            temp->next->prev = temp1->next; 
        } else {
        // If x is a last node
            temp->next = NULL;
        }
    }
}

Remove duplicates from an unsorted linked list Solved on: April 24th 2020

C++

Node * removeDuplicates( Node *head) 
{
    Node *temp = head;
    Node *temp1 = head;
    Node *prev = head;
    vector <int> v;
    vector<int>::iterator it;
    
    while (temp){
        v.push_back(temp->data);
        temp = temp->next;
    }
	
	// referance https://www.techiedelight.com/remove-duplicates-vector-cpp/
	unordered_set<int> s;
	auto end = copy_if(v.begin(), v.end(), v.begin(),
							[&s](int const &i) {
								return s.insert(i).second;
							});

	v.erase(end, v.end());
	
     for (auto i = v.begin(); i != v.end(); i++) {
        temp1->data = *i;
        prev = temp1;
        temp1 = temp1->next;
    }
    prev->next = NULL;

    return head;
}

Merge two sorted linked lists Learnt on: 21st July 2020

C++

Node* sortedMerge(Node* head_A, Node* head_B) {  
    if (!head_A){
        return head_B;
    }
    if (!head_B){
        return head_A;;
    }
    if (head_A->data < head_B->data) {
        head_A->next = sortedMerge(head_A->next, head_B);
        return head_A;
    }
    else {
        head_B->next = sortedMerge(head_A, head_B->next);
        return head_B;
    }
} 

C++

Intersection Point in Y Shapped Linked Lists Solved on: 21st July 2020

int intersectPoint(Node* head1, Node* head2) {
    int c1=0;
    int c2=0;
    Node *temp1= head1;
    Node *temp2= head2;
    while (temp1) {
        c1++;
        temp1=temp1->next;
    }
    while (temp2){
        c2++;
        temp2=temp2->next;
    }
    int c = (c1-c2);
    int i;
    // cout <<c<< ": count\n" ;
    if (c>=0) {
        for (i=0;i<c;i++){
            head1=head1->next;
        }
    } else {
        c=c*-1;
        for (i=0;i<c;i++){
            head2=head2->next;
        }
    }
    while (head1 != NULL && head2 != NULL) {
        if (head1 == head2) {
            return head1->data;
        }
        head1=head1->next;
        head2=head2->next;
    }
    return -1;
    
}

Pairwise swap elements of a linked list Solved on: Jul 22nd 2020

Node* pairWiseSwap(struct Node* head) {
    Node *temp = head;
    
    while (temp != NULL && temp->next != NULL) {
        swap (temp->data, temp->next->data);
        temp = temp->next->next;
    }
    return head;
}