The Gateway to Computer Science Excellence
+2 votes
882 views
Given a linked list :

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?
in Algorithm Challenges by Boss (32.5k points)
edited by | 882 views

2 Answers

+4 votes
Best answer
struct node* swap(struct node * head,struct node * tail)
{
        if(tail -> next != NULL)
                head = swap(head, tail->next);
        if(head == NULL)
                return NULL;
        tail -> next = head -> next;
        head->next = tail;
        head = tail -> next;
        if(head == tail){//End of recursion
                tail -> next = NULL;
                return NULL;
        }
        return head;
}

}
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
	scanf("%d", &((*head)->data));
	(*head) -> next = NULL;
	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)
		head = swap(head, tail->next);
	if(head == NULL)
		return NULL;
	tail -> next = head -> next;
	head->next = tail;
	head = tail -> next;
	if(head == tail){//End of recursion
		tail -> next = NULL;
		return NULL;
	}
	return head;
}
void printlist(struct node *head)
{
	printf("The current list is: \n");
	while(head != NULL){
		printf("%d\t", head-> data);
		head = head->next;
	}
	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 (424k 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
0 votes
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.2k points)
edited by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,475 answers
195,395 comments
100,379 users