Detecting a loop in the linklist?

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.

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;
}

Reversing the first N elements of a linklist in C?

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;
    }
}

Reversing a LinkList in C?

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.

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;
    }
}

Detecting a loop in the linklist?

Your comment on this post:

Related Articles