898 views

1->2->3->4->5->6,

make the following changes
1->6->2->5->3->4

What would be the most effiicient way to make this change?

edited | 898 views

struct node* swap(struct node * head,struct node * tail)
{
if(tail -> next != NULL)
return NULL;
tail -> next = head -> next;
tail -> next = NULL;
return NULL;
}
}

}
1 2 3 4 5 6; head is at 1, tail is at 6
1 6 2 3 4 5; head is at 2, tail is at 5
1 6 2 5 3 4; head is at 3; tail is at 4
1 6 2 5 3 4; head is at 4; tail is at 4 stop here.


Full code:

/*Input the no. of items in list as parameter*/
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node * next;
};
void initialize(struct node** head, int n)
{
if(n == 0)
return;
printf("Enter the numbers of the list...\n");
*head = malloc(sizeof(struct node)); //Our initial list now points to a valid memory location which is the start of the list
struct node *trav = *head; //Trav is used to complete the list, keeping head at beginning.
int i = 0;
while(++i < n)
{
trav ->next = malloc(sizeof(struct node));
trav = trav -> next;
scanf("%d", &trav->data);
trav -> next = NULL;
}
//Nothing to return as *head is updated at beginning
}
struct node* swap(struct node * head,struct node * tail)
{
if(tail -> next != NULL)
return NULL;
tail -> next = head -> next;
tail -> next = NULL;
return NULL;
}
}
{
printf("The current list is: \n");
}
printf("\n");
}
int main(int argc, char* argv[])
{
if(argc < 2)
{
fprintf(stderr, "Please enter no. of items as parameter...\n");
exit(0);
}
struct node * list;
initialize(&list, atoi(argv[1]));
printlist(list);
printf("Modifying....\n");
swap(list, list->next);
printlist(list);

}

by Veteran (431k points)
selected by
0
Sir why r u using argc ,argv in main()?
+1
I dont want to say "Please input n" :P
0
I'm using recursion to keep track of the list order. This is not needed if the list is doubly linked and even for a singly linked list can be handled by explicitly copying them to a new list. Recursion makes the code shorter.
+1
Power of recursion!!

Thanks for this nice solution!!
0

arjun sir i m not able to enter inside recursion...hav doubt. m not able to execute below line second time

if(tail -> next != NULL)
head = swap(head, tail->next); 

this line is executed only once and ..and it is false initially bcoz

we know that

if(tail -> next = NULL)

now how reach this line again as there is no loop and recursion is also not reached.

0
@Tauhin initially second element is passed to the function, not the actual tail.
0
ok
What I did is, I copied the values of linked list to an array :D Then I put the values back to linked list as per requirement. Anyway recursion will also cost you space ...array too ...so my argument is clear..

void fun(struct node *root)
{
int a[100];
struct node *t=root->next;
int c=1,i=0,j=0;
while(t!=NULL)
{
a[i]=t->value;
i++;
t=t->next;
}
t=root->next;
c=1;
j=0;
i--;
while(t!=NULL)
{
if(c%2==1)
{
t->value=a[i];
i--;
}
else
{
t->value=a[j];
j++;
}
c++;
t=t->next;
}
}
by Boss (12.4k points)
edited by