Linked List Collection




/*
Intersection of two Sorted Linked Lists
Given two lists sorted in increasing order, create and return a new list representing the intersection of the two lists.
The new list should be made with its own memory — the original lists should not be changed.
For example, let the first linked list be 1->2->3->4->6 and second linked list be 2->4->6->8, then your function should create and
return a third list as 2->4->6.
*/
node* sortedIntersect(node* a, node* b)
{
      if (a == NULL||b == NULL)
      {
            return (NULL);
      }
      if (a->data <b->data)
      {
            return sortedIntersect(a->next, b);
      }
      if (a->data >b->data)
      {
            return sortedIntersect(a, b->next);
      }
      node* temp = (node*)malloc(sizeof(node));
      temp->data = a->data;
      temp->next = sortedIntersect(a->next, b->next);

      return temp;
}
/* Link list node */
struct Node
{
    int data;
    struct Node* next;
};

typedef struct Node node;
  
/* Given a reference (pointer to pointer) to the head
  of a list and an int, push a new node on the front
  of the list. */
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node =
            (struct Node*) malloc(sizeof(struct Node));
    new_node->data  = new_data;
    new_node->next = (*head_ref);
    (*head_ref)    = new_node;
}
/* Drier program to test count function*/
int main()
{
    /* Start with the empty list */
    struct Node* head1 = NULL;
  
    /* Use push() to construct below list
     1->2->3->4->5 */
    push(&head1, 6);
    push(&head1, 4);
    push(&head1, 3);
    push(&head1, 2);
    push(&head1, 1);

      struct Node* head2 = NULL;
      push(&head2, 8);
    push(&head2, 6);
    push(&head2, 4);
    push(&head2, 2);


    node*temp = sortedIntersect(head1, head2);
      while(temp!=NULL)
      {
            cout<<temp->data<<" ";
            temp = temp->next;
      }
    getchar();
    return 0;
}


/* Link list node */
struct Node
{
    int data;
    struct Node* next;
};
  
/* Given a reference (pointer to pointer) to the head
  of a list and an int, push a new node on the front
  of the list. */
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node =
            (struct Node*) malloc(sizeof(struct Node));
    new_node->data  = new_data;
    new_node->next = (*head_ref);
    (*head_ref)    = new_node;
}
  
/* Counts no. of nodes in linked list */
int getCount(struct Node* head)
{
    int count = 0;  // Initialize count
    struct Node* current = head;  // Initialize current
    while (current != NULL) 

    {
        count++;
        current = current->next;
    }
    return count;
}
  
/* Takes head pointer of the linked list and index
    as arguments and return data at index*/
int getNth(struct Node* head, int n)
{
    struct Node* curr = head;
    for (int i=0; i<n-1 && curr != NULL; i++)
       curr = curr->next;
    return curr->data;
}
 /*
  Printing the data in reverse order using stack
*/ 
void printReverse(Node *head)
{
    // store Node addresses in stack
    stack<Node *> stk; 
    Node* ptr = head;
    while (ptr != NULL) 
    {
        stk.push(ptr);
        ptr = ptr->next;
    }
 
    // print data from stack
    while (!stk.empty())
    {
        cout << stk.top()->data << " ";
        stk.pop(); // pop after print
    }
    cout << "\n";
}
/*
Reverse a linked list using a recurssion
*/
void reverse(struct Node **headref)
{
      struct Node *first;
      struct Node *rest;
      first = *headref;
      rest = first->next;
      if (first == NULL ||rest == NULL)
      {
            return;
      }
      reverse(&rest);
      first->next->next = first;
      first->next = NULL;
      *headref = rest;
}
  
/* Drier program to test count function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
  
    /* Use push() to construct below list
     1->2->3->4->5 */
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
  
    //printReverse(head);

      reverse(&head);
      struct Node *temp = head;
      while(temp!=NULL)
      {
            cout<<temp->data<<" ";
            temp = temp->next;
      }

    getchar();
    return 0;

}







































































































Comments

Post a Comment

Popular posts from this blog

Important Program Collection

C/C++ Greedy Algorithm Programs C/C++ Program Activity Selection Problem C/C++ Program Kruskal’s Minimum Spanning Tree Algorithm C/C++ Program for Huffman Coding C/C++ Program for Efficient Huffman Coding for Sorted Input C/C++ Program for Prim’s Minimum Spanning Tree (MST) C/C++ Program for Prim’s MST for Adjacency List Representation C/C++ Program for Dijkstra’s shortest path algorithm C/C++ Program for Dijkstra’s Algorithm for Adjacency List Representation C/C++ Program for Graph Coloring C/C++ Program for Rearrange a string so that all same characters become d distance away C/C++ Backtracking Programs C/C++ Program to print all permutations of a given string C/C++ Program The Knight’s tour problem C/C++ Program for Rat in a Maze C/C++ Program for N Queen Problem C/C++ Program for Subset Sum C/C++ Program for m Coloring Problem C/C++ Program for Hamiltonian Cycle C/C++ Program for Sudoku C/C++ Program for Tug of War C/C++ Program for (S
Read more

[16 Feb 2020] Given an array where every element occurs three times, except one element which occurs only once.

Find the element that appears once Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space. Examples : Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3} Output: 2 In the given array all element appear three times except 2 which appears once. Input: arr[] = {10, 20, 10, 30, 10, 30, 30} Output: 20 In the given array all element appear three times except 20 which appears once. Following is another O(n) time complexity and O(1) extra space method suggested by aj. We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence. Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000 Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0; Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of
Read more

Which data structure is used in redo-undo feature?

Explanation:  Stack data structure is most suitable to implement redo-undo feature. This is because the stack is implemented with LIFO(last in first out) order which is equivalent to redo-undo feature i.e. the last re-do is undo first. Consider a situation where a client receives packets from a server. There may be differences in speed of the client and the server. Which data structure is best suited for synchronization? (A)  Circular Linked List (B)  Queue (C)  Stack (D)  Priority Queue Answer:   (B) Explanation:  Since packets need to be processed in First In First Out order, a queue can be used for synchronization. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. o Delection of the smallest element o Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose? (
Read more