Linked List : gfg and other selected Ques

    find nth position from last:
          1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 21 22 23 24 25 
     e.g  4th pos from last=> using A.P. an from last= L+(n-1)d =>  L+(n-1)(-1) => L-n+1  
            25-4+1 => 22 

n’th node from the end of a Linked List  

using above concept:
 // check if value of n is not
    // more than length of the linked list
    if (len < n)  return;
 
   Node* temp = head;
 
    // get the (len-n+1)th node from the beginning
    for (i = 1; i < len - n + 1; i++)
        temp = temp->next;
 
    cout << temp->data;

using recursion:

void printNthFromLast( Node* head, int n)
{
  int i = 0;
  if (head == NULL)
    return;
  printNthFromLast(head->next, n);
// ++i recursion ke baad use krne se yah last me jahan recursion
// pahuncha udhar se increment n times for nth pos, yani bottom to up
  if (++i == n)
    cout<<head->data;
}
Two Pointer approach: best and imp

//Function to find the data of nth node from the end of a linked list.
int getNthFromLast(struct Node *head, int n)
{
      struct Node* slow=head;
      struct Node* fast=head;
      for(int i=0;i<n;i++){
          if(fast) fast=fast->next;
          else return -1;
      }
      while(fast){
          fast=fast->next;
          slow=slow->next;
      }
      return slow->data;   
}

Find the middle of a given linked list:similiar to above ques(my first placement interview ques)


worst Approch: Traverse the whole linked list and count the no. of nodes. Now traverse the list again till count/2 and return the node at count/2.
Best Approch:   two pointer approach
Traverse linked list using two pointers. Move one pointer by one and the other pointers by two. When the fast pointer reaches the end slow pointer will reach the middle of the linked list.

int getMiddle(Node *head)
{
   Node* slow=head;
   Node* fast=head;
   while(fast->next){
       if(fast->next->next) fast=fast->next->next;
       else fast=fast->next;  //when  fast reach at node before last
       
       slow=slow->next;
   }
   return slow->data;
}  

Detect loop in a linked list



bool detectLoop(struct Node* head)
{
    unordered_set<Node*> s;
    while (head) {
        // If this node is already present
        // in hashmap it means there is a cycle
        // (Because you we encountering the
        // node for the second time).
        if (s.find(head) != s.end())
            return true;
 
        // If we are seeing the node for
        // the first time, insert it in hash
        s.insert(head);
 
        head = head->next;
    }
 
    return false;
}

two pointer approach: Floyd’s Cycle-Finding Algorithm 
  • Move one pointer(slow_p) by one and another pointer(fast_p) by two.
  • If these pointers meet at the same node then there is a loop. If pointers do not meet then linked list doesn’t have a loop.
    bool detectLoop(Node* head)
    {
       Node* slow=head;
       Node* fast=head;
       while(fast&&fast->next){
           fast=fast->next->next;
      
           slow=slow->next;
           if(slow==fast) return true;
       }
       return false;
    }

remove loop in Linked List:




void detectAndRemoveLoop(Node* head)
{
    // If list is empty or has only one node
    // without loop
    if (head == NULL || head->next == NULL)
        return;
 
    Node *slow = head, *fast = head;
 
    // Move slow and fast 1 and 2 steps
    // ahead respectively.
    slow = slow->next;
    fast = fast->next->next;
 
    // Search for loop using slow and
    // fast pointers
    while (fast && fast->next) {
        if (slow == fast)
            break;
        slow = slow->next;
        fast = fast->next->next;
    }
 
    /* If loop exists */
    if (slow == fast)
    {
        slow = head;
           
        // this check is needed when slow
        // and fast both meet at the head of the LL
          // eg: 1->2->3->4->5 and then
        // 5->next = 1 i.e the head of the LL
          if(slow == fast) {
              while(fast->next != slow) fast = fast->next;
        }
          else {
            while (slow->next != fast->next) {
                slow = slow->next;
                fast = fast->next;
            }
        }
 
        /* since fast->next is the looping point */
        fast->next = NULL; /* remove loop */
    }
}

check if a singly linked list is palindrome   

stack approach:    e.g list is  1 2 3 4 5
            stack also becomes  top to bottom 5 4 3 2 1 bcz 1 pushed first => now match

bool isPalin(Node* head){
         
        // Temp pointer
        Node* slow= head;
        // Declare a stack
        stack <int> s;
        // Push all elements of the list
        // to the stack
        while(slow != NULL){
                s.push(slow->data);
 
                // Move ahead
                slow = slow->ptr;
        } 
        // Iterate in the list again and
        // check by popping from the stack
        while(head != NULL ){
             
            // Get the top most element
             int i=s.top();
             // Pop the element
             s.pop();
             // Check if data is not
             // same as popped element
            if(head -> data != i){
                return false;
            }
            // Move ahead
           head=head->ptr;
        }
 
return true;
}

also here in M4 is map solution

reverse Linked List using Recursion:




Node* revList(Node* head){

     if(!head || !head->next)  return head;

     Node* roL=revList(head->next);
     Node* nxt=head->next;
     nxt->next=head;
     head->next=NULL;
return roL;
}

revList using stack: Easy

Node* revList(Node* head){

    stack<Node*> st;
    Node* tmp=head;
    while(tmp->next){  // tmp->next isliye taki loop ke baad tmp end me pahunch jaye
        st.push(tmp);
        tmp=tmp->next;
    }
    //now tmp reach at end
    head=tmp;
    while(!st.empty()){
           tmp->next=st.top();
           tmp=tmp->next;
           st.pop();
    }
    tmp->next=NULL;
    return head;
}


Remove duplicates from a sorted linked list

For example if the linked list is 11->11->11->21->43->43->60 then removeDuplicates() should convert the list to 11->21->43->60. 
void removeDuplicates(struct Node* head)
{
     struct Node* curr=head;
     struct Node* nxt=NULL;
      while(curr->next){//traverse till end
          nxt=curr->next;
          if(curr->data==nxt->data){
              nxt=nxt->next;
              free(curr->next);
              curr->next=nxt;
              continue;
          }    
          curr=curr->next;
  
      } 
}

Remove duplicates from unsorted linked list

For example if the linked list is 12->11->12->21->41->43->21 then removeDuplicates() should convert the list to 12->11->21->41->43. 

Add 1 to a number represented as linked list 


Input:
LinkedList: 4->5->6
Output: 457
Input:
LinkedList: 4->5->9
Output: 460
Input:
LinkedList: 9->9->9
Output: 1000
it is also a application of revList
 Node* revList(Node* head){
        if(!head) return NULL;
        stack<Node*> st;
        Node* tmp=head;
        while(tmp->next){
            st.push(tmp);
            tmp=tmp->next;
        }
        // now tmp at end 
        head=tmp;
        while(!st.empty()){
                 tmp->next=st.top();
                 tmp=tmp->next;
                 st.pop();
        }
        tmp->next=NULL;
        return head;
    }
    Node* addOne(Node *head) 
    {
        head=revList(head);
        Node* tmp=head;
        Node* prevTotmp;
        
        while(tmp&&tmp->data==9){
            tmp->data=0;
            prevTotmp=tmp;
            tmp=tmp->next;
        }
        if(tmp) tmp->data=(tmp->data)+1;
        if(!tmp){
              Node* newNode=new Node(1);
            newNode->data=1;
            newNode->next=NULL;
            prevTotmp->next=newNode;
        }
        head=revList(head);
        return head;
        
    }


here is the gfg best sol


    struct Node* addTwoLists(struct Node* f_head, struct Node* s_head)
    {
             f_head=revList(f_head);
             s_head=revList(s_head);
             struct Node* tmp1=f_head;
             struct Node* tmp2=s_head;
             struct Node* prev;
             int sum=0;
             int carry=0;
             struct Node* head_to_return=new Node(0);
             struct Node* tmp=head_to_return;
             while(tmp1&&tmp2){
                struct Node* newNode=new Node(0);
                 int sum=tmp1->data+tmp2->data;
                 if(carry){
                   sum+=carry;
                   carry=0;
                 } 
                 if(sum>9){
                     carry=sum/10;
                     sum=sum%10;

                 }
                 tmp->data=sum;
             
                 tmp->next=newNode;
                 prev=tmp;
                 tmp=tmp->next;
                 tmp1=tmp1->next;
                 tmp2=tmp2->next;
                 
             }
             // both list are of equal length
            if(!tmp1 && !tmp2){
                // add only whwen carry left
                if(carry){  
                     tmp->data=carry;
                     carry=0;
                }
                 
            }
             while(tmp1){
                struct Node* newNode=new Node(0);
                 int sum=tmp1->data;
                 if(carry){
                   sum+=carry;
                   carry=0;
                 } 
                 if(sum>9){
                     carry=sum/10;
                     sum=sum%10;

                 }
                 tmp->data=sum;
                 tmp->next=newNode;
                 prev=tmp;
                 tmp=tmp->next;
                 tmp1=tmp1->next;
                  
             }
                 while(tmp2){
                 struct Node* newNode=new Node(0);
                 int sum=tmp2->data;
                 if(carry){
                   sum+=carry;
                   carry=0;
                 } 
                 if(sum>9){
                     carry=sum/10;
                     sum=sum%10;

                 }
                 tmp->data=sum;
                 tmp->next=newNode;
                 prev=tmp;
                 tmp=tmp->next;
                 tmp2=tmp2->next;
                  
             }
             // add only whwen carry left
              if(carry){  
                   tmp->data=carry;
                   carry=0;
                }
             if(tmp->data==0){
                 free(tmp);
                 prev->next=NULL;
             }
             
             head_to_return=revList(head_to_return);
             return head_to_return;
         
    }

Intersection Point in Y Shapped Linked Lists:



int intersectPoint(Node* head1, Node* head2)
{
    Node* tmp1=head1;
    Node* tmp2=head2;
    //if one of them is NULL
    if(!tmp1 || !tmp2) return -1;
    while(tmp1!=tmp2){      //if here is intersection, end loop
        tmp1=tmp1->next;
        tmp2=tmp2->next;
        if(tmp1==tmp2){   // if here is intersection, return
            return tmp1->data;
        }
        //if one of them becomes NULL, move to another head(complexity purpose)
        if(!tmp1) tmp1=head2;
        if(!tmp2) tmp2=head1;
        
    }
    // if loop end , and not return 
    return tmp1->data;
}

merge sort in arr:

void merge(int* arr,int l,int mid,int r){
           int tmp[r-l+1]; // e.g. total ele from 2 to 7 is 6 (7-2+1)
           int i=l,j=mid+1;// second arr start from mid+1 isliye j=mid+1 
           int k=0;
           while(i<=mid && j<=r){
                 if(arr[i]==arr[j]){
                  // tricky jb equal tb dono ko rkhna hoga bhai
                  tmp[k++]=arr[i++];
                  tmp[k++]=arr[j++];
                 }else if(arr[i]<arr[j]){
                     tmp[k++]=arr[i++];
                 }else{
                    tmp[k++]=arr[j++];
                 }
           }
           while(i<=mid){
               tmp[k++]=arr[i++];
           }
           while(j<=r){
            tmp[k++]=arr[j++];
           }
 
         // store tmp ele to arr 
           for(int i=l;i<=r;i++) {
            arr[i]=tmp[i-l];
            // cout<<arr[i]<<" ";
          }
       
  
}


void mergeSort(int* arr,int l,int r){
         if(l>=r) return;
         int mid=(l+r)/2;
         // split in two parts
         mergeSort(arr,l,mid);
         mergeSort(arr,mid+1,r);
         // merge sorted parts
         merge(arr,l,mid,r);


}


------

Comments

Post a Comment

Popular posts from this blog

c++ oops

Image
   class:   It is a user-defined data type, which holds its own data members and member functions, which can be accessed and used by creating an instance of that class. A class is like a blueprint for an object. blue-print representing a group of objects which shares some common properties and behaviours. object: An Object is an instance of a Class. When a class is defined, no memory is allocated but when it is instantiated (i.e. an object is created) memory is allocated. Member Functions in Classes There are 2 ways to define a member function: Inside class definition Outside class definition To define a member function outside the class definition we have to use the scope resolution :: operator along with class name and function name. C++ Constructor: A constructor in C++ is a special ‘MEMBER FUNCTION’ having the same name as that of its class which is used to initialize some valid values to the data members of an object. It is executed automatically whenever an object o...
Read more

Takeoff (hackerearth.3, datastructure, array 1-D)

      There are three planes  A ,  B  and  C . Plane  A  will takeoff on every  p t h  day i.e.  p ,  2 p ,  3 p  and so on. Plane  B  will takeoff on every  q t h  day and plane  C  will takeoff on every  r t h  day. There is only one runway and the takeoff timing is same for each of the three planes on each day. Your task is to find out the maximum number of flights that will successfully takeoff in the period of  N  days. Note:  If there is collision between the flights no flight will take off on that day. Input Format The first line of the input contains a single integer  T , the number of test cases. Then  T  lines follow each containing four space-separated integers  N ,  p ,  q  and  r  as denoted in the statement. Output Format For each test case print a single integer representing the maximum num...
Read more

Aptitude tricks

Image
                                                                                    Time and Work 1.      Work from Days: If A can do a piece of work in  n  days, then A's 1 day's work = 1 . n 2.      Days from Work: If A's 1 day's work = 1 , then A can finish the work in  n  days. n 3.      Ratio: If A is thrice as good a workman as B, then: Ratio of work done by A and B = 3 : 1. Ratio of times taken by A and B to fin...
Read more