Difference between revisions of "Interview Preparation Linked List"

typedef struct linked_list_node {
    struct linked_list_node *next;
    int data;
} linked_list_t;

#include <stdlib.h> /* malloc() */


/* Assume this is a source file, such as linked_list.c */
/* g for "global" variable of this file, and static for "private variable" of this file */
static linked_list_t *g_head = NULL;


void ll_allocate_head(int  n)
{
    g_head = malloc(sizeof(*g_head));
    g_head->data = n;
    g_head->next = NULL;
}

void ll_add_to_beg(int n)
{
    if (NULL == g_head) {
        ll_allocate_head(n);
    }
    else {
        linked_list_t *new_elm = malloc(sizeof(linked_list_t));

        /* Copy the data, and set this node's next to the older head */
        new_elm->next = g_head;
        new_elm->data = n;
 
        /* Head becomes this element since we wanted to add to beginning */
        g_head = new_elm;
    }
}

void ll_add_to_end(int n)
{
    if (NULL == g_head) {
        ll_allocate_head(n);
    }
    else {
        /* Need to get to the tail first */
        linked_list_t *tail = g_head;
        while(tail->next != NULL) {
            tail = tail->next;
        }

        linked_list_t *new_elm = malloc(sizeof(linked_list_t));
        new_elm->next = NULL;
        new_elm->data = n;

        /* Simply add new element to the tail */
        tail->next = new_elm;
    }
}

#include <stdlib.h> /* malloc() */

/*Function to reverse a singly linked list by iterating through the list*/
void ll_reverse(linked_list_t** data)
{
    linked_list_t* prev   = NULL;      /*previous node is made NULL*/
    linked_list_t* g_head= *data;      /*data is assigned to head node*/
    linked_list_t* next;
    while (g_head)
    {
        next  = g_head->next;        
        g_head->next = prev;   
        prev = g_head;
        g_head= next;
    }
    *data= prev;
}

#include <stdlib.h> /* malloc() */

/*Function to detect a loop in a singly linked list by iterating through the list by using two pointers
Slow pointer -> steps through each node
Fast pointer -> Skips every other node
*/
bool ll_loop(linked_list_t* head)
{
    linked_list_t *slow= head, *fast = head;
    
    while((slow!=NULL)&&(fast->next!=NULL)&&(fast!=NULL))//checking to see if the current position or the
    {                                                           //successive position is pointing to a NULL.
        slow = slow-> next;         //slow pointer
        fast = fast->next->next;    //fast pointer
        if(slow==fast){             //comparing to see if the slow and fast pointers meet at a node.
            return TRUE;            //return true if the loop exists
        }
    }
    return FALSE;                   //return false if the loop doesnt exists.
}

#include <stdlib.h> /* malloc() */


/* Assume this is a source file, such as linked_list.c */
/* g for "global" variable of this file, and static for "private variable" of this file */
static linked_list_t *g_head = NULL;


void remove_dups(linked_list_t* head){ //we are never deleting the head node
     
     linked_list_t* current = head;  //current node
     linked_list_t *pointer1, *duplicate;

     while(current->next != NULL){//traversing the list pointed by current 
          pointer1 = current;// the current node is copied into pointer1
          while(pointer1->next != NULL){// traversing the list pointed by pointer1
                if(pointer1->next->data == current->data){ //Checking for duplicates by comparing the current data and pointer1 data of next node
                   duplicate = pointer1->next;// copy the address of pointer1 node (which contains duplicate data) into duplicate
                   pointer1->next = pointer1->next->next;//placing the new address i.e. the next node address into pointer to which it will be pointing next
                   free(duplicate);//free the duplicate node (which contains duplicate data)
                   }
                   pointer1 = pointer1->next;//move to the next node
                }
           current = current->next;//current pointing to next node
          
          }
     }

}

#include <stdlib.h> /* malloc() */


/* Assume this is a source file, such as linked_list.c */
/* g for "global" variable of this file, and static for "private variable" of this file */
static linked_list_t *g_head = NULL;


bool isPalindrome(linked_list_t *head){
     linked_list_t *reverse = reverse(head);// calling function to reverse the list
     return checkPalindrome(head,reverse);// calling function to check if the list is Palindrome
}

linked_list_t* reverse(linked_list_t *head1){
     linked_list_t *temp = NULL;

     while(head1->next != NULL){
     linked_list_t *new_reverse_node = (linked_list_t*)malloc(sizeof(linked_list_t));// new node create to copy the current list in reverse order
     new_reverse_node->data = head1->data;// copy head data into new node
     new_reverse_node->next = temp;//reversing the list by making the first node the last node
     temp = new_reverse_node;
     head1 = head1->next;//traverse till the end of the list
     }
     return temp;
}

bool checkPalindrome(linked_list_t *list1, linked_list_t *list2){
     while(list1->next != NULL && list2->next != NULL){
     if(list1->data != list2->data){
     return false;
     }
     list1 = list1->next;
     list2 = list2->next;
     }
     if(list1->next == NULL && list2->next == NULL){
     return true;
     }
}

typedef struct linked_list_node {
    struct linked_list_node *next;    /*next node*/
    struct linked_list_node* prev;    /*previous node*/
    int data;
} linked_list_t;

/* Assume this is a source file, such as linked_list.c */
/* g for "global" variable of this file, and static for "private variable" of this file */

static linked_list_t *g_head = NULL;

/*new node is created and a pointer is returned  */

linked_list_t *create_new_node(int n ) {
  linked_list_t *new_node
    = malloc(sizeof(linked_list_t));    /*creating a new node*/
  new_node->data = n;                   /*assigning input to data*/
  new_node->prev = NULL;               /*previous and next links are initialized to NULL*/
  new_node->next = NULL;
  return new_node;        /*returning a pointer*/
}

/*Inserting node at head */
void insert_at_head(int n) {
  linked_list_t* new_node = create_new_node(n);        /*creating a new node*/

  if(g_head == NULL) {                                 /*condition to check if the head node is empty*/
    g_head = new_node;                                  
    return;
  } 

  g_head->prev = new_node;   /*assigning new node to head node */       
  new_node->next = g_head; 
  g_head = new_node;
}

/*to insert a node at tail*/
void insert_at_tail(int n) {
  linked_list_t* temp = g_head;
  linked_list_t* new_node = create_new_node(n);        //creating a new node

  if(g_head == NULL) {
    g_head = new_node;
    return;
  }

  while(temp->next != NULL) temp = temp->next;  //last node
  temp->next = new_node;
  new_node->prev = temp;
}

typedef struct linked_list_node {
    struct linked_list_node *next;    /*next node*/
    int data;
} linked_list_t;

void delete_node(linked_list_t *g_head, linked_list_t *N)
{
    /* to delete head node */
    if(g_head == N)
    {
        if(g_head->next == NULL)
        {
            return;
        }
 
        /* Copy next node data to head node */
        g_head->data = g_head->next->data;
 
        /* copy address of next node to N*/
        N = g_head->next;
 
        /* delete next node */
        g_head->next = g_head->next->next;
 
        free(N);
        return;
    }
  
    /* to delete a node other than the first(head) node */
    /*previous node */
    linked_list_t *prev = g_head;
    while(prev->next != NULL && prev->next != N)
        prev = prev->next;
 
   /*check if prev node exists */
    if(prev->next == NULL)
    {
        return;
    }
 
    /*Delete that node from Linked List
    prev->next = prev->next->next;
 
    free(N);
 
    return; 
}

bool member_of(const int value, const list<int>& my_list, list<int>::const_iterator it)
{
    if (it == my_list.end()) 
    	return false;
    return (*it == value) || member_of(value, my_list, ++it);
}

void isListUnique(list<int>& alist)
{
    if (alist.size() <= 1) return; // base case

    int first = alist.front();
    alist.erase(alist.begin());  // remove the first element

    isListUnique(alist);  // make the rest of the list unique

    if (!member_of(first, alist, alist.begin()))
    {
        alist.push_front(first);  // put back the first element
    }
}

void listReverse(list<int>& my_list)
{
    if (my_list.size() <= 1) return; // base case

    int first = my_list.front();
    my_list.erase(my_list.begin());  // remove the first element

    listReverse(my_list);          // reverse the rest of the list
    my_list.push_back(first);  // append the first element at the end
}