Linked List Problems ( My Program of the Day Series :-) )

Write a program to Remove duplicates in an unsorted linked list .

Initially we need a driver program to create a linked list and print it.

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *next;
};

struct node * allot (int data)
{
    struct node * temp = NULL;
    temp = (struct node *) malloc (sizeof (struct node));
    temp->next = NULL;
    temp->data = data;
    return temp;
}

void append(struct node **head , int data)
{
    struct node *trav = NULL;
    if ( *head == NULL)
    {
        *head = allot(data);
    }
    else
    {
        trav = *head;
        while ( trav->next != NULL )
            (trav)=trav->next;
        trav->next = allot(data);
    }
}

void print(struct node *head)
{
    if (head == NULL)
    printf("empty list !!");
    else
    {
        while(head)
        {
            printf("%d->",head->data);
            head=head->next;
        }
        printf("Null \n");
    }
}


}
int  main ()
{
    struct node *head = NULL;
    //creating linked list
    append(&head,1);
    append(&head,2);
    append(&head,3);
    append(&head,2);
          append(&head,8);
    append(&head,1);
    append(&head,9);
    //printing a linked list
       print(head);
    removedup(head);
       print(head);
       return 0;
} 

Now the code to remove duplicates

void removedup(struct node *head)
{
    struct node * a = NULL;
    struct node * b = NULL;

    if (!head || !(head->next) )
        return ;
    while (head)
    {
        a = head;
        b = head->next;
        while (b)
        {
            if (head->data == b->data) {
            a->next = b->next;
            b->next = NULL;
            free(b);
            b=a->next;
            }
            else {
                a=b;
                b=b->next;
            }
        }
        head = head->next;
    }

Question from Cracking the coding interview question
Section linked lists
2.1  Write code to remove duplicates from an unsorted linked list.

Now the code to find Nth node of linked list from end of list

// VERSION 1 from my own thinking...

void findn_end( 
struct node *head , int n )
{
    int size=0, index=1;
    struct node *trav = head;
    if (head == NULL)
        return;
    if (n  <= 0)
        return;
    //find Size
    while (trav)
    {
        size++;
        trav = trav->next;
    }
    printf("size of list is %d n is %d\n", size , n);

    if (n > size)
        return;

    for(trav=head,index=1; index < (size-n+1);index++)
        trav=trav->next;
    printf("ntn node is %d\n",trav->data);
}

Cracking the coding interview -- Q 2.2 Implement an algorithm to find the nth to last element of a singly linked list.