Thursday, July 12, 2012

K - Reverse linked list program

Below is the C code for reversing each k-elements in the linked list.
Example: for k value 3
Input:  1->2->3->4->4->5->6->7->8
Output: 3->2->1->6->5->4->8->7
#include<stdio.h>
#include<stdlib.h>
struct node
{
 int info;
 struct node *next;
};

typedef struct node Node;

Node* append(Node *h, int info)
{
 Node *tempHead=h;
 Node *newNode = (Node*)malloc(sizeof(Node));
 newNode->info = info;
 newNode->next = NULL;
 if(tempHead == NULL) // if the list has zero elements. make new node as a head
 {
  h=newNode;
 }
 else if(tempHead->next==NULL)  // if the list is having only one node
 {
  tempHead->next = newNode;
 }
 else
 {
  Node *tempNode = h;
  while(tempNode->next != NULL)  // if the list has more than one node, so moving to the last node
  {
   tempNode = tempNode->next;
  }
  tempNode->next = newNode; // appending the new node at the end
 }
 if(info == 101) // this is for making the list circular
 newNode->next = h;
 return h;
// printf("temp -> info is %d\n",temp->info);
}


/*****************************************************************************
for displaying the nodes in the list
*****************************************************************************/
void display(Node *h)
{
 Node *temp = h;
 while (temp->next!=NULL)
 {
  printf("%d->",temp->info);
  temp = temp->next;
 }
 printf("%d\n",temp->info);
}

/*****************************************************************************
This function reverse each  K-nodes in the list. e.g for k=3
input:  1->2->3->4->4->5->6->7->8
result: 3->2->1->6->5->4->8->7
*****************************************************************************/
Node *kreverse(Node *head, int k)
{
 Node *temp_head,*new_head,*tail,*temp;
 int k_temp = k;
 new_head = head;
 head = head->next;
 new_head->next = NULL;
 tail = new_head;
 while(head && k_temp-1)
 {
  temp = head->next;
  head->next = new_head;
  new_head = head;
  head = temp;
  k_temp--;
 }
 k_temp = k;
 while(head)
 {
  temp = head->next;
  head->next = NULL;
  tail->next = head;
  temp_head = tail;
  tail = head;
  head = temp;
  while(head && k_temp-1)
  {
   temp = head->next;
   head->next = temp_head->next;
   temp_head->next = head;
   head = temp;
   k_temp--;
  }
  temp_head = tail;
  k_temp = k;
 }
 return new_head;
}

main()
{
 Node *head = NULL;
 int i;
 for (i=1;i<=20;i++)
 {
  head = append(head,i*10);
 }
 display(head);
 head =  kreverse(head,3);
 display(head);

}

No comments:

Popular Posts