CareerCup

# include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
int info;
struct node*link;
}*NODE;

int display(NODE head)
{
while(head!=NULL)
{
printf("%d",head->info);
head=head->link;
}
return 0;
}//end of display
NODE exchange(int n,NODE head)
{
NODE prev,temp,p,q,r,s;
int count=1,i,c=1;
if(head==NULL)
return head;
//find the number of modes
for(p=head;p->link!=NULL;p=p->link)
{
prev=p;
count++;
}
printf("count%d",count);//debugging
if(n>=count)
{
puts("you exceed the number of nodes present in the list");
exit(1);
}
//when i will come out of this loop p will point to the last node
if(n==1)
{//we need to swap first and last node

prev->link=head;
p->link=head->link;
head->link=NULL;
head=p;
}
else
{
//need to find those nodes
i=count-n;
p=head;
while(c<n||c<=i)
{
if(c<n)
temp=p;
if(c<=i)
prev=p;
p=p->link;
c++;
}//end of while loop
//we need to swap q and r
q=temp->link;
r=prev->link;
s=q->link;
temp->link=r;
if(prev!=q)
{//no condition of loop arises
prev->link=q;
q->link=r->link;
r->link=s;
}
else
{
q->link=r->link;
r->link=q;
}


}//end of else
return head;
}//end of function
NODE insert(int n)
{
NODE t,start=NULL;
int i,item;
for(i=0;i<n;i++)
{
t=(NODE)malloc(sizeof(struct node));
if(t==NULL)
{
puts("NOT ENUF SPACE");
return NULL;
}
printf("enter info item");
scanf("%d",&item);
t->info=item;
t->link=start;
start=t;
}//end of for loop
return start;
}//end of insert
int main()
{
int n,m;
NODE head;
printf("enter the number of elements you want to enter");
scanf("%d",&n);
head=insert(n);
printf("enter the n to be exchanged");
scanf("%d",&m);
head=exchange(m,head);
printf("returned");
display(head);
getch();
return 0;
}//end of main function

In this solution you can exchange the two nodes within a single traversal of the linked list. Not syntactically correct.
The premise is that if there are n nodes in the linked list, the head node is the nth node from the end.

assumption: single linked list
head = pointer to head of the list
n = nth node from start and end

n_start = null //pointer to nth node from start
n_start_prev = null //pointer to node whose next points to n_start
n_end = null //pointer to nth node from end
n_end_prev = null //pointer to node whose next points to n_end
temp = null //temporary pointer used while swapping
ptr = head //starting point of traversal
ptr_prev = null //points to previous node of ptr
count = 0 // stores which number of node we are pointing to during traversal

if(ptr == null){
	//empty linked list, exit
}

//traversal of linked list
//find n_start and n_end
while(ptr!=null){
	count++;
	if(count == n){
		n_start = ptr;
		n_start_prev = ptr_prev;
		n_end = head;
		n_end_prev = null;
	}
	else if(count > n){
		n_end_prev = n_end;
		n_end = n_end->next;
	}
	ptr_prev = ptr;
	ptr = ptr->next;
}

if(count < n){
	//not enough nodes in linked list, exit
}

//do the swapping now
if(n_start_prev != null){
	n_start_prev->next = n_end;
}

if(n_end_prev != null){
	n_end_prev->next = n_start;
}

temp = n_start->next;
n_start->next = n_end->next;
n_end->next = temp;

1. nth node from beginning can be initialized easily by a linear n-iteration walk.
2. For nth node from end, initialize 2 separate pointers one at the beginning and the other one n-steps away (can use another pointer by assigning the one from step 1)
3. Now, keep on performing node = node.next for both pointers of step 2 till the later pointer of step 2 hits null which assures that the 1st pointer of step 2 is now n steps from the end. Discard the 2nd pointer of step 2.
4. Now perform simple pointer swapping operations to change the positions of step 1 pointer and step 3 pointer.
5. Need to check for boundary conditions such as if the list length is less than n then the operation cannot be performed.

int i=0;
node *x = NULL;
node *y = NULL;
node* cur = root;
while (cur) {
    if (i == n-1) {
        x = cur;
        y = root;
    }
    else if (i>=n) 
        y = y->next;
    cur = cur->next;
    i++;
}
swap(x, y);

void swap(int n)
	{
		 //n-- position to swap
		Link previousNodefromfirst = head;
		for(int i=1;i<n-1;i++)
		{
			previousNodefromfirst = previousNodefromfirst.next;
		}
		Link previousNodefromlast = head;
		//10 is the size of the list.taking previous node
		for(int i=0;i<9-n;i++)
		{
			previousNodefromlast = previousNodefromlast.next;
		}
		Link firstCurrent = previousNodefromfirst.next;
		Link latNext = previousNodefromlast.next.next;
		
		previousNodefromfirst.next = previousNodefromlast.next;
		previousNodefromlast.next.next = firstCurrent.next;
		
		previousNodefromlast.next = firstCurrent;
		firstCurrent.next = latNext;
		this.display();
		
	}

void SwapNthPointers(struct node **head ,int n)
{
struct node *node = *head;
struct node *first_pointer = node,*second_pointer = node,*third_pointer = NULL,*fourth_pointer = NULL;

int index = 1;


while( node->next != NULL)
{
if(index <= n-2 )
{
first_pointer = first_pointer->next;
}

if(index >= n+1 )
{
second_pointer = second_pointer->next;
}

node = node->next;
index++;
}

third_pointer = first_pointer->next;
fourth_pointer = second_pointer->next;

first_pointer->next = fourth_pointer;
fourth_pointer = first_pointer->next->next;
first_pointer->next->next = third_pointer->next;


second_pointer->next = third_pointer;
third_pointer->next = fourth_pointer;

}

My code is of O(n) Complexity. But takes space for the extra pointers

//Here is the Java Solution .. Please provide your comments..

class Lnode {
int data;
Lnode link;

public Lnode(int val) {
data = val;
link = null;
}
}

public class Kswap {

public void createList(Lnode temp, int val) {
if (temp == null)
temp = new Lnode(val);
while (temp.link != null)
temp = temp.link;

temp.link = new Lnode(val);
}

public void printList(Lnode node) {
while (node != null) {
System.out.println(node.data);
node = node.link;
}
}

public Lnode kswap(Lnode start,int k) {

int length=length(start);
if(k>length){
System.out.println("Greater than list length");
return null;
}else if(k==length){
if(length == 2){
Lnode temp;
temp=start.link;
temp.link=start;
start.link=null;
return temp;
}else{
Lnode startNext;
Lnode lastBefore;
Lnode newParent;
startNext = start.link;
lastBefore = lastBeforeElement(start);
newParent=lastBefore.link;
lastBefore.link.link=startNext;
lastBefore.link = start;
start.link=null;
return newParent;
}
}else{
Lnode startBefore;
Lnode startNext;
Lnode endBefore;
Lnode endNext;
Lnode temp;
startBefore = kBeforeNode(start, k);
endBefore = kBeforeNode(start, length-k+1);
temp=endBefore.link;

startNext = startBefore.link.link;
endNext=endBefore.link.link;
endBefore.link=startBefore.link;
endBefore.link.link=endNext;
startBefore.link=temp;
startBefore.link.link=startNext;
return start;
}



}
public Lnode kBeforeNode(Lnode node,int k) {
if (node == null)
return null;
int loop=1;
while (loop<k-1) {
node = node.link;
loop++;
}
return node;
}

public Lnode lastBeforeElement(Lnode node) {
if (node == null)
return null;
while (node.link.link != null) {
node = node.link;
}
return node;
}

public static int length(Lnode node) {
int length = 0;
while (node != null) {
length++;
node = node.link;
}
return length;
}

public static void main(String args[]) {
Lnode start = new Lnode(4);
Kswap k = new Kswap();
k.createList(start, 7);
k.createList(start, 54);
k.createList(start, 3);
k.createList(start, 55);
k.createList(start, 8);
k.createList(start, 9);
k.createList(start, 10);
k.printList(start);
start = k.kswap(start, 3);
System.out.println("After Swapping :: ");
k.printList(start);
}
}