top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

    Get Free Article Updates

Facebook Login
Site Registration

Comparing two linklist if they are Same?

+1 vote
89 views

Two linklist are same if and only if both the linklist contains same elements at same position.

LinkList Comparison

Sample Code

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

struct node *head;
int length= 0;

int list_size()
{
    printf("\n No. of elements in the list: %d", length);
    return length;
}

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void add_node(int data)
{
    struct node *new;
    new = create_node(data);

    if (head == NULL)
    {
        head = new;
    }
    else
    {
        new->next = head;
        head = new;
    }
}

int compare (struct node *first, struct node *second)
{
    while (first != NULL && second != NULL)
    {
        if (first->num != second-> num)
        {
            return 0;
        }
        else
        {
            first = first->next;
            second = second->next;
        }
    }

    if (first != NULL || second != NULL)
    {
        return 0; // length of two linklist is not same
    }
    else
    {
        return 1;
    }
}
posted Sep 10, 2014 by Salil Agrawal

  Promote This Article
Facebook Share Button Twitter Share Button LinkedIn Share Button


Related Articles

This program only first n elements of a linked list as compare to whole reverse as discussed in the http://tech.queryhome.com/57009/reversing-a-linklist-in-c . In this program we are manipulating the pointers only in place of data swap.

Sample Code

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

struct node *head;
int length= 0;

int list_size()
{
    printf("\n No. of elements in the list: %d", length);
    return length;
}

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void add_node(int data)
{
    struct node *new;
    new = create_node(data);

    if (head == NULL)
    {
        head = new;
    }
    else
    {
        new->next = head;
        head = new;
    }
}

void display_list()
{
    struct node *temp_head;

    temp_head = head;

    if (temp_head == NULL)
    {
        printf("List is empty");
        return;
    }

    while (temp_head != NULL)
    {
        printf("%d ", temp_head->data);
        temp_head = temp_head->next;
    }
} 

void reverse(struct node **head, int n)
{
    struct node *p, *q, *r;

    p = q = r = *head;

    if (n > 0) // If N is zero then no need to reverse 
    {
        p = p->next->next;
        q = q->next;
        r->next = NULL;
        q->next = r;

        while (n > 0 && p != NULL) // Run a loop for n times only 
        {
            r = q;
            q = p;
            p = p->next;
            q->next = r;
            n--;
        }
        *head = q;
    }
}
READ MORE

Algorithm:
1. Traverse linked list using two pointers called slow pointer and fast pointer.
2. Move slow pointer by one in each iteration and fast pointer by two.
3. If these pointers meet then there is a loop. If pointers do not meet then linked list doesn’t have loop.

Linklist with a Loop

Sample Code

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

struct node *head;
int length= 0;

int list_size()
{
    printf("\n No. of elements in List : %d", length);
    return length;
}

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void add_node(int data)
{
    struct node *new;
    new = create_node(data);

    if (head == NULL)
    {
        head = new;
    }
    else
    {
        new->next = head;
        head = new;
    }
}

void display_list()
{
    struct node *temp_head;

    temp_head = head;

    if (temp_head == NULL)
    {
        printf("List is empty");
        return;
    }

    while (temp_head != NULL)
    {
        printf("%d ", temp_head->data);
        temp_head = temp_head->next;
    }
}  

int detect_loop(struct node *head)
{
  struct node  *slow_pointer = head, *fast_pointer = head;

  while(slow_pointer && fast_pointer && fast_pointer->next )
  {
    slow_pointer = slow_pointer->next;
    fast_pointer = fast_pointer->next->next;

    if (slow_pointer == fast_pointer)
    {
       printf("Found Loop");
       return 1;
    }
  }
  return 0;
}
READ MORE

A circular linklist is the linklist whose last node points to the head node in place of null.
LinkList

To convert a linklist to circular linklist we need to find the last node i.e. the node which is pointing to null and make it to point at the head.

Sample Implementation

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

struct node *head;
int length= 0;

int list_size()
{
    printf("\n No. of elements in List : %d", length);
    return length;
}

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void add_node(int data)
{
    struct node *new;
    new = create_node(data);

    if (head == NULL)
    {
        head = new;
    }
    else
    {
        new->next = head;
        head = new;
    }
}

void to_circular(struct node **p)
{
    struct node *rear;

    rear = *p;
    while (rear->next != NULL)
    {
        rear = rear->next;
    }
    rear->next = *p;
}

// Should be called after converting to circular only
void display_list() 
{
    struct node *temp_head;

    temp_head = head;

    if (temp_head == NULL)
    {
        printf("List is empty");
        return;
    }

    while (temp_head != head)
    {
        printf("%d ", temp_head->data);
        temp_head = temp_head->next;
    }
}  
READ MORE

What is Queue
Queue is a abstract data type with two operation add_data(enque) and get_data(deque) and provides the data in the form of its arrival or simply it maintains the first in first out machenism (FIFO). Data is always added to its top and retrieved from its rear.

Queue ADT

Required Functions

int queue_size()
struct node * create_node(int data)
void add_data(int data)
int get_data()
void traverse_queue()

Sample Code

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

struct node *top, *rear;
int length= 0;

int queue_size()
{
    printf("\n No. of elements in queue : %d", length);
    return length;
}

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void add_data(int data)
{
    struct node *new;
    new = create_node(data);

    if ((top == NULL) && (rear == NULL))
    {
        top = new;
        rear = new;
    }
    else
    {
        top->next = new;
        top = new;
    }
}

int get_data()
{
    struct node *temp_rear;
    int ret_val;

    temp_rear = rear;

    if (temp_rear == NULL)
    {
        printf("\n Error : Trying to pop from empty queue");
        return -1;  // Assuming -1 as error
    }
    else
    {
        temp_rear = temp_rear->next;
    }

    printf("\n Popped value : %d", rear->data);
    ret_val = rear->data;

    free(rear);
    rear = temp_rear;

    length--;
    return ret_val;
}

void traverse_queue()
{
    struct node *temp_rear;

    temp_rear = top;

    if (temp_rear == NULL)
    {
        printf("Queue is empty");
        return;
    }

    while (temp_rear != NULL)
    {
        printf("%d ", temp_rear->data);
        temp_rear = temp_rear->next;
    }
} 
READ MORE

What is Link List
W linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a link to the next node in the sequence.
LinkList

Reversing a LinkList
Reversing a link list can be done in two ways one by swapping the data values and another is by manipulating only the pointers, in this article I am discussing only the pointer manipulation mechanism in recursive and non-recursive ways.

Sample Code

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

struct node *head;
int length= 0;

int list_size()
{
    printf("\n No. of elements in the list: %d", length);
    return length;
}

struct node * create_node(int data)
{
    struct node *new;

    new = (struct node*)malloc(sizeof(struct node));
    new->next = null;
    new->data = data;

    length++;

    return new;
}

void add_node(int data)
{
    struct node *new;
    new = create_node(data);

    if (head == NULL)
    {
        head = new;
    }
    else
    {
        new->next = head;
        head = new;
    }
}

void display_list()
{
    struct node *temp_head;

    temp_head = head;

    if (temp_head == NULL)
    {
        printf("List is empty");
        return;
    }

    while (temp_head != NULL)
    {
        printf("%d ", temp_head->data);
        temp_head = temp_head->next;
    }
} 

void reverse_list()
{
    struct node *p, *q, *r;

    p = q = r = head;
    p = p->next->next;
    q = q->next;
    r->next = NULL;
    q->next = r;

    while (p != NULL)
    {
        r = q;
        q = p;
        p = p->next;
        q->next = r;
    }
    *head = q;
}

void reverse_list_recursion(struct node **phead)
{

    // Storing the head into local head variable 
    struct node *lhead = *phead;

    if (lhead && lhead->next) {
        *phead = lhead->next;
        reverse_list_recursion(phead);
        lhead->next->next = lhead;
        lhead->next = NULL;
    }
}
READ MORE
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...