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;
    linked_list_t* g_head= *data;
    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 reverse a singly linked list by iterating through the list*/
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){
     
     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(pointer->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(pointer1);//free the pointer1 node (which contains duplicate data)
                   }
                else{
                   pointer1 = pointer1->next;//pointing to 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;
     }
}