CareerCup

This can be done in line without first completely traversing the list to check the size. This can be done with 3 pointers.

One pointer is for the first element which is k from the start
the second pointer is for the element which is k from the end
the last pointer is to find the end.

Then you traverse the list save the pointers and do the swap at the end, you don't even have to mess with the links when swapping, just swap the values from the pointers you have saved from above.

node * ptr1, *ptr2, *ptr3;
count = 0;
ptr3 = head;

while( ptr3->next != null ){
   count++;

   if( count == k ){
      ptr1 = ptr3;
      ptr2 = head;
   
   } else if (count > k){
      ptr2 = ptr2->next;   
   }

   ptr3 = ptr3->next;
}

if(count < k){
   // print that there was an error because the list size was too small
   return null;
}
else if( ptr1 != null && ptr2 != null){
   int temp = ptr1->data;
   ptr1->data = ptr2->data;
   ptr2->data = temp;

   return head;
}

return null;

public static void swap(LinkedList<Integer> ll,int k){
		int size = ll.size();
		if(1<=k&&k<=size){
			int firstK = ll.get(k-1);
			int lastK=ll.get(size-k);
			ll.set(k-1, lastK);
			ll.set(size-k, firstK);
			System.out.println(ll);
		}else{
			System.out.println("ERROR");
		}

}

We need to handle a few test cases.
1. Both nodes are end nodes.
2. Both nodes are adjacent.
3. Both nodes are somewhere else.
4. Both node are same.
5. kth node doesn't exist.

I prefer swapping the nodes rather than values. It is always advisable to swap the nodes as in general, nodes may contain several data. So, it will be overhead to swap the values.

Steps:
Find the kth node[p] from the beginning. If no kth node, return.
Take another pointer[q] & move it at head. Move it & the kth node one step at a time until kth node is null. q is the kth node from the last.

We need to swap p & q.
The part of linked list found is: t1->p->t2 and t3->q->t4
Just swap the nodes based on links & handle the corner cases mentioned above.
Here is the code:

void swap(struct node **root,int k)
{
        int count=1;
        struct node *t1,*t2,*t3,*t4,*cur,*p,*q;
        if(!(*root) || !k)
                return;
 
        cur=*root;
        
        t1=t2=t3=t4=NULL;
        while(cur && count++!=k)
        {
                t1=cur;
                cur=cur->next;
        }
        if(count<=k) //not enough nodes
                return;
        p=cur;
        q=*root;
 
        while(cur && cur->next)
        {
                t3=q;
                q=q->next;
                cur=cur->next;
        }
        t2=p->next;
        t4=q->next;
        
        if(p==q) // both nodes are same
                return;
        
        if(p->next==q) // adjacent nodes
        {
                t1->next=q;
                q->next=p;
                p->next=t4;
        }       
        else if(q->next==p) // adjacent nodes
        {
                t3->next=p;
                p->next=q;
                q->next=t2;
        }
        
        else if(!t1) // p is the first node
        {
                *root=(*root)->next;
                q->next=*root;
                *root=q;
                p->next=t4;
                t3->next=p;
        }
        else if(!t3) // q is the last node
        {
                *root=(*root)->next;
                p->next=*root;
                *root=p;
                q->next=t2;
                t1->next=q;
        }
        else
        {
                p->next=t4;
                t3->next=p;
                q->next=t2;
                t1->next=q;
        }
}
See the complete code here: ideone.com/bUqR3

Take 3 pointers to the starting point of the list - P1, P2 & P3.

Start moving P1 & P3 till you have moved 'K' nodes. If the list ends before P1 reaches the End, give the error message "LIST IS OF LESSER SIZE".
Once you have reached the Kth node, move P1 and P2 pointers to the next node one by one till P1 reaches the end.

At this point P2 points to the Kth element from the last.
Now simply swap the values of P2 & P3.

Job done.

Algorithm:
1.Get the linked list lenghth. If it is less than 'K' print the error message. O(N)
2.Traverse to the 'K' the element from the beginning. O(N)
3.Traverse to the N-Kth element from the beginning. O(N)
4. Swap them.O(1)
5.End of Algorithm

Complexity:
O(N).

1. Find Kth Element from Beginning. Store the pointer.
2. Using Kth Element, find kth element from last(two pointers)
3. Swap these pointers.
4. At every step, check for length traversed till is < n, otherwise raise error

Node* SwapList(Node* head, int k)
{
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	
	Node* current = head->next;
	Node* prev = head;
	int currentCount = 2;
	
	Node* kth = NULL;
	Node* kthPrev = NULL;
	Node* kthLast = NULL;
	Node* kthLastPrev = NULL;
	
	while (current != NULL)
	{
		if (currentCount == k)
		{
			kth = current;
			kthPrev = prev;
		}
		
		if (kthLast != NULL)
		{
			kthLastPrev = kthLast;
			kthLast = kthLast->next;
		}
		else if (kth != NULL)
		{
			kthLast = head;
		}
		
		prev = current;
		current = current -> next;
	}
	
	if (kth == NULL) return head; // kth node does not exist in list
	if (kth == head) // k == 1
	{
		kthLast->next = kth->next
		kth->next = NULL;
		kthLastPrev->next = kth;
		return kthLast; // this becomes new head
	}
	
	
	if (kthLast == head)
	{
		kth->next = kthLast->next;
		kthprev->next = kthLast;
		kthLast->next = NULL;
		return kth;
	}
	
	Node* temp = kth->next;
	kth->next = kthLast->next;
	kthLast->next = temp;
	kthLastPrev->next = kth;
	kthPrev->next = kthLast;
	return head;
}

Node* SwapList(Node* head, int k)
{
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	
	Node* current = head->next;
	Node* prev = head;
	int currentCount = 2;
	
	Node* kth = NULL;
	Node* kthPrev = NULL;
	Node* kthLast = NULL;
	Node* kthLastPrev = NULL;
	
	while (current != NULL)
	{
		if (currentCount == k)
		{
			kth = current;
			kthPrev = prev;
		}
		
		if (kthLast != NULL)
		{
			kthLastPrev = kthLast;
			kthLast = kthLast->next;
		}
		else if (kth != NULL)
		{
			kthLast = head;
		}
		
		prev = current;
		current = current -> next;
	}
	
	if (kth == NULL) return head; // kth node does not exist in list
	if (kth == head) // k == 1
	{
		kthLast->next = kth->next
		kth->next = NULL;
		kthLastPrev->next = kth;
		return kthLast; // this becomes new head
	}
	
	
	if (kthLast == head)
	{
		kth->next = kthLast->next;
		kthprev->next = kthLast;
		kthLast->next = NULL;
		return kth;
	}
	
	Node* temp = kth->next;
	kth->next = kthLast->next;
	kthLast->next = temp;
	kthLastPrev->next = kth;
	kthPrev->next = kthLast;
	return head;
}

Node* SwapList(Node* head, int k)
{
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	
	Node* current = head->next;
	Node* prev = head;
	int currentCount = 2;
	
	Node* kth = NULL;
	Node* kthPrev = NULL;
	Node* kthLast = NULL;
	Node* kthLastPrev = NULL;
	
	while (current != NULL)
	{
		if (currentCount == k)
		{
			kth = current;
			kthPrev = prev;
		}
		
		if (kthLast != NULL)
		{
			kthLastPrev = kthLast;
			kthLast = kthLast->next;
		}
		else if (kth != NULL)
		{
			kthLast = head;
		}
		
		prev = current;
		current = current -> next;
	}
	
	if (kth == NULL) return head; // kth node does not exist in list
	if (kth == head) // k == 1
	{
		kthLast->next = kth->next
		kth->next = NULL;
		kthLastPrev->next = kth;
		return kthLast; // this becomes new head
	}
	
	
	if (kthLast == head)
	{
		kth->next = kthLast->next;
		kthprev->next = kthLast;
		kthLast->next = NULL;
		return kth;
	}
	
	Node* temp = kth->next;
	kth->next = kthLast->next;
	kthLast->next = temp;
	kthLastPrev->next = kth;
	kthPrev->next = kthLast;
	return head;
}

Node* SwapList(Node* head, int k)
{
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	
	Node* current = head->next;
	Node* prev = head;
	int currentCount = 2;
	
	Node* kth = NULL;
	Node* kthPrev = NULL;
	Node* kthLast = NULL;
	Node* kthLastPrev = NULL;
	
	while (current != NULL)
	{
		if (currentCount == k)
		{
			kth = current;
			kthPrev = prev;
		}
		
		if (kthLast != NULL)
		{
			kthLastPrev = kthLast;
			kthLast = kthLast->next;
		}
		else if (kth != NULL)
		{
			kthLast = head;
		}
		
		prev = current;
		current = current -> next;
	}
	
	if (kth == NULL) return head; // kth node does not exist in list
	if (kth == head) // k == 1
	{
		kthLast->next = kth->next
		kth->next = NULL;
		kthLastPrev->next = kth;
		return kthLast; // this becomes new head
	}
	
	
	if (kthLast == head)
	{
		kth->next = kthLast->next;
		kthprev->next = kthLast;
		kthLast->next = NULL;
		return kth;
	}
	
	Node* temp = kth->next;
	kth->next = kthLast->next;
	kthLast->next = temp;
	kthLastPrev->next = kth;
	kthPrev->next = kthLast;
	return head;
}

public void swapElementsInLinkedList(int k){
if(k<0 || k> getSize() ){
throw new InvalifIndexException("LIST IS OF LESSER SIZE/LIST SIZE CANT BE NEGATIVE");
}
temp = head ;
LinkedListNode KthnodeFromRear = null;
int newValueForK = (getSize()-k)+1;
int counter = 1;
int firstStop = 0;
int lastStop = 0;
if(k<newValueForK){
firstStop = k;
lastStop = newValueForK;
}
else{
firstStop = newValueForK;
lastStop = k;
}
while(counter != firstStop){
counter ++;
temp=temp.getNext();
}
KthnodeFromRear = temp;
while(counter!=lastStop){
counter ++ ;
KthnodeFromRear = KthnodeFromRear.getNext();
}
swap(temp,KthnodeFromRear);
}


private void swap(LinkedListNode first, LinkedListNode last) {
Integer data = first.getData();
first.setData(last.getData());
last.setData(data);
}

void replace_node(struct node **head,int pos)
{
        int count = 1;
        int tmp =0;
        myNode *curr = *head;
        myNode *one = curr;
        myNode *two = curr;
        while(two != NULL && two->next !=NULL && count <pos)
        {
                two = two->next;
                count++;
        }
        curr = two;
        while(one!=NULL &&one->next!=NULL&& two->next!=NULL)
        {
                one = one->next;
                two = two->next;
        }
        tmp = curr->value;
        curr->value = one->value;
        curr = one;
        curr->value = tmp;
}

void replace_node(struct node **head,int pos)
{
        int count = 1;
        int tmp =0;
        myNode *curr = *head;
        myNode *one = curr;
        myNode *two = curr;
        while(two != NULL && two->next !=NULL && count <pos)
        {
                two = two->next;
                count++;
        }
        curr = two;
        while(one!=NULL &&one->next!=NULL&& two->next!=NULL)
        {
                one = one->next;
                two = two->next;
        }
        tmp = curr->value;
        curr->value = one->value;
        curr = one;
        curr->value = tmp;
}

int kthnodeswap (node*& head, int k)
{

    if (k<=0) //invalid node given
        return -1;
    else
    {
        if (k==1) //swap head node and last when index = 1
        {
            node *trav = head;

            //move till the end of the list
            while (trav->next!=NULL)
                trav = trav->next;

            //swap head and last node
            int temp = head->data;
            head->data = trav->data;
            trav->data = temp;
            return 1;
        }
        else
        {
            node *trav = head; //pointer to traverse the list
            node *swap1 = trav; //pointer which will point to the kth node from beginning
            node *swap2 = trav; //pointer which will point to the kth node from end

            //advance both traverse pointer and the beginning pointer till kth node
            for (int i = 2; i <= k ; i++) //index starts at 2 since 1st node is head
            {
                trav = trav->next;
                if (trav == NULL) return 0; //list is of lesser size
                swap1 = trav; //advance two pointers to the same location
            }

            //after reaching the kth node from beginning advance the traverse pointer and end pointer
            while (trav->next != NULL)
            {
                trav = trav->next;
                swap2 = swap2->next;
            }

            //swap the data pointed by beginning pointer and end pointer
            int temp = swap1->data;
            swap1->data = swap2->data;
            swap2->data = temp;
            return 1;

        }
    }
}

int list_swap(snode *head,int pos)
{
    snode *tmp;
    int ll=0;
    int cnt=1;
    snode *curr    =    NULL;

    for(tmp = head;tmp;tmp=tmp->next) 
            ll++;
    
    for(tmp = head;cnt < pos;cnt++) 
            tmp=tmp->next;

    /*Found from head node*/
    
    curr    =    tmp;
    while((ll-cnt) != pos-1)
    {
        tmp    =    tmp->next;
        cnt++;
    }
    /*Now swapping the data part*/
    cnt    =    tmp->data;
    tmp->data    =    curr->data;
    curr->data    =    cnt;
    return(0);

}

void swaplist(Node** list,int K)
{
	if (K<1) 
		return;
	int count=1;
	Node* first=*list;
	while (count++<K && first) 
		first=first->next;
	if (first==0) {
		cout << "not available\n";
		return;
	}
	Node* tmp=first;
	first=first->next;
	Node* second=*list;
	while (first) {
		first=first->next;
		second=second->next;
	}
	swap(tmp1,second);

}

This is working code and covers almost all the cases and boundries:

void kSwap(node** head)
{
  clrscr();
  if(*head == NULL)
  {
    printf("\nlist is empty");
    getch();
    return;
  }
  if((*head)->link == NULL)
  {
    printf("\nList has only one element");
    getch();
    return;
  }
  printf("Enter the value of k: ");
  int k;
  scanf("%d",&k);
  if(k<=0)
  {
    printf("\n K cannot be less than 1. Please try again");
    getch();
    kSwap(&(*head));
  }
  int len = length(*head);
  if(k>len)
  {
    printf("\n value of k cannot be larger than the length of list.\n please try again");
    getch();
    kSwap(&(*head));
  }

  node* startNode = *head;
  node* endNode = *head;
  int data=0;
  if(len%2 == 1 && (len+1)/2 == k) //list has odd number of elements and we are trying to swap middle one.
  {
    printf("\nswapping the same element");
    getch();
    return;
  }
  if(len == 2)//only two elements so either k=1 or k=2, elements will be swapped
  {
    data = startNode->data;
    startNode->data = startNode->link->data;
    startNode->link->data = data;
    return;
  }
  int start = 2;
  int end = 2;
  while(start<k)//moving start pointer just one node before the actual node
  {
    startNode = startNode->link;
    start++;
  }
  while(end<len+1-k)//moving the end pointer just one node before the actual node
  {
    endNode = endNode->link;
    end++;
  }
  if(k == 1)//handling the extreme corner case when k=1 because it involve header manipulation
  {
    data = endNode->link->data;
    endNode->link->data = startNode->data;
    startNode->data = data;
    return;
  }
  else if(k == len)//handling the extreme corner case when k=length because it involve header manipulation
  {
    data = endNode->data;
    endNode->data = startNode->link->data;
    startNode->link->data = data;
    return;
  }
  else
  {
    data = startNode->link->data;
    startNode->link->data = endNode->link->data;
    endNode->link->data = data;
    return;
  }
}

Fellas.. this ain't a Big Complex Code.. Its tricky question...

Algo.
1> Get kth Node from last and kth node from beginning.
2> Hold one pointer each to these nodes.
3> Swap their values.. :D

Code

struct Node* Swapkth(struct Node * node,int k)
{
struct Node *temp1,*temp2,*temp3;
temp1=node;
while(k!=0) {
node=node->next;
}
temp2=node;// this is kth node from first

while(node->next!=NULL) {
node=node->next;
temp1=temp1->next;
}
//Finally when loop exits temp1 will be pointing to the kth node from the last.
temp3=temp1;
temp1->data=temp2->data;
temp2->data=temp3->data;
free(temp1);
free(temp2);
free(temp3);
}


This is all U need... No Swapping No Complex Code..

Fellas.. this ain't a Big Complex Code.. Its tricky question...

Algo.
1> Get kth Node from last and kth node from beginning.
2> Hold one pointer each to these nodes.
3> Swap their values.. :D

Code

struct Node* Swapkth(struct Node * node,int k)
{
struct Node *temp1,*temp2,*temp3;
temp1=node;
while(k!=0) {
node=node->next;
}
temp2=node;// this is kth node from first

while(node->next!=NULL) {
node=node->next;
temp1=temp1->next;
}
//Finally when loop exits temp1 will be pointing to the kth node from the last.
temp3=temp1;
temp1->data=temp2->data;
temp2->data=temp3->data;
free(temp1);
free(temp2);
free(temp3);
}


This is all U need... No Swapping No Complex Code..

/*Q1.- Written exam (Amazon, Bangalore)

Given a singly link list and a number 'K', swap the Kth node from the start with the Kth node from the last. Check all the edge cases.

Sample Input: 1->2->3->4->5->6->7->8 and K = 3
Sample Output : 1->2->6->4->5->3->7->8

Sample Input: 1->2->3->4->5->6->7->8 and K = 10
Sample Output: print error "LIST IS OF LESSER SIZE"*/
#include<stdio.h>
#include<malloc.h>
struct node *recursion(struct node *,int );
/*
void append(struct node **,int );
void display(struct node *);

here is problem is that void you will get warning
warning: ‘struct node’ declared inside parameter list [enabled by default]
amazon1.c:12:20: warning: its scope is only this definition or declaration, which is probably not what you want [enabled by default]
amazon1.c:13:21: warning: ‘struct node’ declared inside parameter list [enabled by default]
*/
struct node
{
int data;
struct node *link;
};
int main()
{
struct node *start;
start=NULL;
int n,i=0,item,k;
printf("Enter the no of node\n");
scanf("%d",&n);
while(i++<n)
{
printf("Enter node value\n");
scanf("%d",&item);
append(&start,item);
}
display(start);
printf("Enter the number k for swaping kth from the fast and kth from last\n");
scanf("%d",&k);
swap(start,k,n);
printf("\n");
display(start);
}
append(struct node **t,int b)
{
struct node *r,*temp;
r=*t;

if(r==NULL)
{
r=(struct node*)malloc(sizeof(struct node));
*t=r;
}
else
{
while(r!=NULL)
{
temp=r;
r=r->link;
}
temp->link=(struct node *)malloc(sizeof(struct node));
r=temp->link;
/*
If you write like this r=(struct node *)malloc(sizeof(struct node)); then you are creating indepent node which are not connected
to it's previous node.r=NULL then r(struct node *)malloc(sizeof(struct node)); it will not link to the previous node .
*/
}
r->data=b;
r->link=NULL;

}
display(struct node *q)
{
while(q!=NULL)
{
printf("%d-> ",q->data);
q=q->link;
}
}
swap(struct node *fast,int k,int n)
{
struct node *Kth_fast,*Kth_last;
int temp;
if(k>n)
printf("Swaping is not possible you enter the number greater than number of element of linklist\n");
else
{
Kth_fast=recursion(fast,k);
Kth_last=recursion(fast,n-k+1);
}
temp=Kth_last->data;
Kth_last->data=Kth_fast->data;
Kth_fast->data=temp;
}
struct node *recursion(struct node *p,int K)
{
int i=1;
while(i++<K)
{
p=p->link;
}
return p;
}

Complexity: O(n)
Space: O(1)

void swapKth(int kth) {
		node *kthfirst = head; //Private member from your linked list class
		node *kfirstPrev = NULL;
		node *temp = head;
		node *kthLast = head;
		node *kthLastPrev = NULL;
		int pos = 1;

		if (kth == 0) {
			cout << "Nothing to do...";
			return;
		}

		while (temp->next != NULL) {
			if (pos < kth) {
				kfirstPrev = kthfirst;
				kthfirst = kthfirst->next;
			}
		

			if (pos >= kth) {
				kthLastPrev = kthLast;
				kthLast = kthLast->next;
			}
			temp = temp->next;
			pos++;
		}

		if (kth > pos) {
			cout << "Invalid length...";
			return;
		}
				
		if (kfirstPrev == NULL) {
			kthLastPrev->next = kthfirst;
			kthLast->next = head->next;
			head = kthLast;
			kthLastPrev->next->next = NULL;
		}
		else {			
			kfirstPrev->next = kthLast;
			kthLastPrev->next = kthfirst;
			temp = kthfirst->next;
			kthfirst->next = kthLast->next;
			kthLast->next = temp;
		}

		return;
	}

Complexity: O(n)
Space: O(1)

void swapKth(int kth) {
		node *kthfirst = head; //Private member from your linked list class
		node *kfirstPrev = NULL;
		node *temp = head;
		node *kthLast = head;
		node *kthLastPrev = NULL;
		int pos = 1;

		if (kth == 0) {
			cout << "Nothing to do...";
			return;
		}

		while (temp->next != NULL) {
			if (pos < kth) {
				kfirstPrev = kthfirst;
				kthfirst = kthfirst->next;
			}
		

			if (pos >= kth) {
				kthLastPrev = kthLast;
				kthLast = kthLast->next;
			}
			temp = temp->next;
			pos++;
		}

		if (kth > pos) {
			cout << "Invalid length...";
			return;
		}
				
		if (kfirstPrev == NULL) {
			kthLastPrev->next = kthfirst;
			kthLast->next = head->next;
			head = kthLast;
			kthLastPrev->next->next = NULL;
		}
		else {			
			kfirstPrev->next = kthLast;
			kthLastPrev->next = kthfirst;
			temp = kthfirst->next;
			kthfirst->next = kthLast->next;
			kthLast->next = temp;
		}

		return;
	}

bool swapKth(Node *head,int k)
{
  int counter=0;
  Node *kth=head,*kth_end=head;
  while(kth && counter++<k) kth=kth->next;
  if(!kth) return false;
  counter=0;
  while(counter ++<k)head=head->next;
  while(head) {head=head->next;kth_end=kth_end->next;}
  swap(kth->data,kth_end->data);
  return true;
}

bool swapKth(Node *head,int k)
{
  int counter=0;
  Node *kth=head,*kth_end=head;
  while(kth && counter++<k) kth=kth->next;
  if(!kth) return false;
  counter=0;
  while(counter ++<k)head=head->next;
  while(head) {head=head->next;kth_end=kth_end->next;}
  swap(kth->data,kth_end->data);
  return true;
}

bool swapKth(Node *head,int k)
{
  int counter=0;
  Node *kth=head,*kth_end=head;
  while(kth && counter++<k) kth=kth->next;
  if(!kth) return false;
  counter=0;
  while(counter ++<k)head=head->next;
  while(head) {head=head->next;kth_end=kth_end->next;}
  swap(kth->data,kth_end->data);
  return true;
}

bool swapKth(Node *head,int k)
{
  int counter=0;
  Node *kth=head,*kth_end=head;
  while(kth && counter++<k) kth=kth->next;
  if(!kth) return false;
  counter=0;
  while(counter ++<k)head=head->next;
  while(head) {head=head->next;kth_end=kth_end->next;}
  swap(kth->data,kth_end->data);
  return true;
}

bool swapKth(Node *head,int k)
{
  int counter=0;
  Node *kth=head,*kth_end=head;
  while(kth && counter++<k) kth=kth->next;
  if(!kth) return false;
  counter=0;
  while(counter ++<k)head=head->next;
  while(head) {head=head->next;kth_end=kth_end->next;}
  swap(kth->data,kth_end->data);
  return true;
}

bool swapKth(Node *head,int k)
{
  int counter=0;
  Node *kth=head,*kth_end=head;
  while(kth && counter++<k) kth=kth->next;
  if(!kth) return false;
  counter=0;
  while(counter ++<k)head=head->next;
  while(head) {head=head->next;kth_end=kth_end->next;}
  swap(kth->data,kth_end->data);
  return true;
}

you can just reverse the value.

if (indexToBeSwapped < 0 || indexToBeSwapped > inputList.Count - 1)
return;
int indexFromLast = inputList.Count - indexToBeSwapped;
int temp = inputList[indexToBeSwapped];
inputList[indexToBeSwapped] = inputList[indexFromLast];
inputList[indexFromLast] = temp;

There is no need to swap the node. Just swap the value. That's it,

bool swapList(Node<int>* head, int k)
{
int count = 0;
Node<int> *p1, *p2, *end;
p1 = p2 = end = head;

while (count < k-1)
{
if (0 != end->next)
{
end = end->next;
count++;
}
else
{
return false;
}
}

p1 = end; // fix the first pointer

while (0 != end->next)
{
end = end->next;
p2 = p2->next;
}// fix the position of second pointer

// swap the data values in the two pointer p1 and p2
p1->data = p1->data + p2->data;
p2->data = p1->data - p2->data;
p1->data = p1->data - p2->data;

p1 = p2 = end = 0;
return true;
}

bool swapList(Node<int>* head, int k)
{
    int count = 0;
    Node<int> *p1, *p2, *end;
    p1 = p2 = end = head;

    while (count < k-1)
    {
        if (0 != end->next)
        {
            end = end->next;
            count++;
        }
        else
        {
            return false;
        }
    }

    p1 = end; // fix the first pointer

    while (0 != end->next)
    {
        end = end->next;
        p2 = p2->next;
    }// fix the position of second pointer

    // swap the data values in the two pointer p1 and p2
    p1->data = p1->data + p2->data;
    p2->data = p1->data - p2->data;
    p1->data = p1->data - p2->data;

    p1 = p2 = end = 0;
    return true;
}

I have written and tested the following code ... its working

bool swapList(Node<int>* head, int k)
{
    int count = 0;
    Node<int> *p1, *p2, *end;
    p1 = p2 = end = head;
    while (count < k-1)
    {
        if (0 != end->next)
        {
            end = end->next;
            count++;
        }
        else
        {
            return false;
        }
    }
    p1 = end; // fix the first pointer
    while (0 != end->next)
    {
        end = end->next;
        p2 = p2->next;
    }// fix the position of second pointer
    // swap the data values in the two pointer p1 and p2
    p1->data = p1->data + p2->data;
    p2->data = p1->data - p2->data;
    p1->data = p1->data - p2->data;
    p1 = p2 = end = 0;
    return true;
}

hi guys , below is the code with 2 pointers..difference between pointers is k...
slow pointer is behind k positions of fast pointers.

There is a check before getting the k(th) element from the first and k(th) element from the last..which you can see in the following loop:

for( i = 1; i< k; i++){
fast = fast.getNext();
if(fast == null){
System.out.println("List is of size:: " + i + " which is lesser then::" + k);
return;
}
}




Please find the code below , this is a method in a linked list class, which access the head of the list using this.getHead() method.

and swaps the values in the last..
public void replaceKthCharacter(int k){

Node kthElementFromStart,slow , fast;
slow = fast = this.getHEAD();

if(slow == null || fast == null){
System.out.println("List is empty..");
return;
}

int i;

for( i = 1; i< k; i++){
fast = fast.getNext();
if(fast == null){
System.out.println("List is of size:: " + i + " which is lesser then::" + k);
return;
}
}

kthElementFromStart = fast ;

while(fast != null && fast.getNext() != null){
fast = fast.getNext();
slow = slow.getNext();
}

String tmpKey = kthElementFromStart.getKey();
kthElementFromStart.setKey(slow.getKey());
slow.setKey(tmpKey);


}

Its Easy, please do as explained below.

1.take 2 pinters say ptr1 and ptr2 and assign the root node address.
2.Move the ptr2 for the k times,this the pointer you have to swap keep the address with you.
3.Now move the both the pointer ptr1 and ptr2 both at time, the moment ptr2 reach to null, note down the ptr1.
4.swap the ptr1 and once node which you have restored before.

complexity is O(n)

#include<iostream.h>
#include<conio.h>
struct node
{
    int info;
    struct node *link;
};
struct node *create(struct node *start, int data);
void exchange(struct node *start, int k);
void display(struct node *start);

int main()
{
 	int data,ans,k;
 	struct node *start=NULL;
 	do
 	{
 	     cout<<"Enter the value"<<endl;
 	     cin>>data;
         start=create(start,data);
         cout<<"do you want to add another node?"<<endl;
         cout<<"enter 1 for yes"<<endl;
         cin>>ans;
    }while(ans==1);
    display(start);
    cout<<"enter the position";
    cin>>k;
    exchange(start,k);
    display(start);
 	getch();
 	return 0;
}

void exchange(struct node *start, int k)
{
 	 int count=0,s,i;
 	 struct node *p,*q,*p1,*q1,*temp;
 	 p=start;
 	 q=p;
 	 while(p!=NULL)
 	 {
          count++;
          p=p->link;
     }
     try
     {
       if(k>count)
         throw k;
     //cout<<endl<<count<<" is the count"<<endl;
     p=start;
     for(i=1;i<k;i++)
     {
		 p1=p;
		 p=p->link;
     }
     s=count-k;
     for(i=0;i<s;i++)
     {
		 q1=q;
		 q=q->link;
     }
     if(p==q1)
     {
 		  int swap;
 		  swap=p->info;
 		  p->info=q->info;
 		  q->info=swap;
 		  return;
     }
     temp=q->link;
     p1->link=q;
     q->link=p->link;
     q1->link=p;
     p->link=temp;
     
     }
     catch(int)
     {
  		 cout<<"out of bounds"<<endl;
     }
}

struct node *create(struct node *start, int data)
{
     struct node *p=start,*temp;
     if(start==NULL)
     {
          start=new node;
          start->info=data;
          start->link=NULL;
          return start;
	 }
	 while(p->link!=NULL)
	 {
          p=p->link;
     }
     temp=new node;
     temp->info=data;
     temp->link=NULL;
     p->link=temp;
     return start;
}

void display(struct node *start)
{
 	 struct node *p=start;
 	 while(p!=NULL)
 	 {
			cout<<p->info;
			if(p->link!=NULL)
			  cout<<"->";
			p=p->link;
     }
     cout<<endl;
}

swapKthNode(node *head){
    temp=head
    while(k!=1){
        if (head == NULL) return "ERROR";
        head = head->next;
        k--;
    }
    first_node=head;
    while(head->next!=NULL){
        head = head->next;
        temp = temp->next;
    }
    second_node = temp;
    swap(first_node->data, second_node->data)


}

// (assuming k=0 means swap root and tail)
Node* swapK (Node* head, int k) {

	Node* p1, p2, temp;
	int n = 1;
	
	// no list, nothing to swap.. 
	if (head == null || head->next = null)
		return head;
	
	// count length of list
	// optimized here to save time for k=0 below
	p1 = head;
	while(p1->next != null) {
		p1 = p1->next;
		n++;
	}
	
	// negative values of k and k greater
	// then length of list are not valid
	if (k < 0 || k > n)
		return NULL;	// should actually throw error here

	// normalize k
	if (k > n/2)
		k = n-k;
		
	// special case if k=0 or k=n
	if (k == 0) {
		// set p1 = 2nd to last node
		p1 = head;
		for (int i = 1; i < n-1; i++)
			p1 = p1->next;
		// set p2 = last node
		p2 = p1->next;
		
		// set last node to point to 2nd node
		p2->next = head->next;
		// set 2nd to last node to point to head
		p1->next = head;
		// set head to point to nothing (it is now the last node)
		head->next = null;
		
		// return the new head (p2)
		return p2;
	}
		
	// set p1 to (k-1)th node
	p1 = head;
	for (int i = 1; i < k; i++) {
		p1 = p1->next;
	}
	// set p2 to (n-k-1)th node
	p2 = p1->next;
	for (int i = k; i < n-2k; i++) {
		p2 = p2->next;
	}
	
	// swap p1's next and p2's next
	temp = p1->next;
	p1->next = p2->next;
	p2->next = p1->next;
	// swap p1 next's next and p2 next's next
	temp = p1->next->next;
	p1->next->next = p2->next->next;
	p2->next->next = p1->next->next;
	
	return head;
}

void fn(node * start)
  {
     if(K>N)// if n given else traverse inO(n) to find the length
       printf("ARRAY IS OF LESSER  SIZE")
    else
   {
        int traverse=0,count=0;
        if(K>N-K)
          traverse=N-K;
       else traverse=K;
      node * one ,*two;
      one=start;
      while(count++!=traverse)
         one=one->next;
      two=one;
     traverse=abs(2*K-N)
     count=0
     while(count++!=traverse)two=two->next
     swap(one->data,two->data);
     }
  }

void move_the_node(struct link_list **node, int mov)
{
struct link_list *start_ptr, *end_ptr, *length_ptr;
int i=0,j;
if((*node)->next == NULL)
printf("No swapping..since list is empty\n");
else
{
length_ptr = (*node);
while(length_ptr)
{
i++;
length_ptr = length_ptr->next;
}
if(i <= mov)
printf("Cant swap..since no enough nodes\n");
else{
end_ptr = start_ptr = (*node);
for(j=0; j<mov; j++)
start_ptr = start_ptr->next;
for(j=0; j<(i-mov-1); j++)
end_ptr = end_ptr->next;
i = end_ptr->data;
end_ptr->data = start_ptr->data;
start_ptr->data = i;
}
}
}

don't u think the question is too easy..

public void swapListNodes(int swapPosition)
{
Node advPointer = first;
Node normalPointer = first;
Node tempNode = first;
Node iterator = first;
int tempdata = 0;
int loop = 1;

if (swapPosition > count) return;

while (loop < swapPosition)
{
if (iterator.next != null)
{
advPointer = iterator.next;
iterator = iterator.next;
loop++;
}
}

tempNode = advPointer; // at 3rd position from start

while (advPointer.next != null)
{
advPointer = advPointer.next;
normalPointer = normalPointer.next;
}


tempdata = normalPointer.data;
normalPointer.data = tempNode.data;
tempNode.data = tempdata;
}

void swapkelement(struct list **l,int k)
{
struct list *x = *l;
struct list *y;
struct list *z = *l;
int i;
for(i=0 ; i < k ; i++)
{
if(x == NULL)
{
printf("LIST IS OF LESSER SIZE");
return;
}
if(i == k-1)
y = x;
x = x->next;
}

while(NULL != x)
{
z = z->next;
x = x->next;
}

i = y->data;
y->data = z->data;
z->data = i;
}

hey guys pls let me know if this is correct solution.....

void swap(nd *start,int val)
{
nd *temp;
int count=0,j,i=0;

temp=start;
while(temp->next!=NULL)
{
temp=temp->next;
count++;
}
if(count>val)
{
j=0;
temp=start;
i=count-val;
while(j++<=i)
{
temp=temp->next;
}
//p("from last %d\n",temp->data);
count=0;
while(count++<val)
{
start=start->next;
}
//p("from beg %d\n",start->data);
//if(start->next==temp) //if both elements are adjacent to each other....
//{
int var;
var=start->data;
start->data=temp->data;
temp->data=var;
//p("list changed...\n");

}

#include<iostream.h>
int k,t1,t2;
int x;
void insert1();
void swap1();
void swap();
struct Node1
{
	int info1;
	Node1 *next1;
};
Node1 *ptr1,*start1=NULL,*rear1,*save1;
main()
{
	cout<<"How many nodes in list\n";
	
	cin>>x;
	for(int i=0;i<x;i++)
	{
		insert1();
	}
	cout<<"Enter the value of K\n";
	
	cin>>k;
	swap1();
	//swap();
}
void insert1()
{
	ptr1=new Node1;
	
	if(start1==NULL)
	{
		cout<<"Enter info\n";
        cin>>ptr1->info1;
		start1=ptr1;
		ptr1->next1=NULL;
		rear1=ptr1;
	}
	else
	{
		cout<<"Enter info\n";
        cin>>ptr1->info1;
		rear1->next1=ptr1;
		ptr1->next1=NULL;
		rear1=ptr1;
	}
}
void swap1()
{
	int cnt=0;
	save1=start1;
	while(save1)
	{
		cnt=cnt+1;
		cout<<"\n"<<"COUNT HERE\n";
		cout<<"\n"<<cnt;
		if(cnt==k)
		{
			t1=save1->info1;
		
		}
			//save1=save1->next1;
		if(cnt==(x-k) )
		{
			t2=save1->info1;
			
		}
		save1=save1->next1;
		
	}
	int temp;
	temp=t1;
	t1=t2;
	t2=temp;
	cout<<"VALUES INTERCHANGED\n\n\n"<<t1<<"\t"<<t2;
	/*save1=start1;
	cout<<start1->info1;
	while(save1)
	{
		save1=save1->next1;
		cout<<"\n"<<save1->info1;
	}
}
void swap()
{
	
}*/
	   	
}

public void swapindex(list L,int index){
List lst=new LinkedList(L);
swap(lst,lst.get(index),lst.get(lst.size()-index));
}

The running time is O(N) and hardly any space complexity .. the only trick here is to maintain the height of the node in the node object and the length of the linked list in the linkedlist instance

Here is the python implementation

def swap_kth_elem(ip_list,k):
	node = ip_list.head
	if k>ip_list.length:
		return "Error message"
	final_pos = None
	while node is not None:
		if final_pos and node.height == final_pos:
			finalnode = node
			break
		elif k == node.height :
			keynode = node
			final_pos = ip_list.length - k + 1
			if final_pos < k:
				node = ip_list.head
				continue
		node = node.next
	keynode.key,finalnode.key = finalnode.key,keynode.key
	return ip_list.print_list()

I simply did this by getting the two nodes from the get node function and then swapped the two. i got the answer correctly.


public LinkedListNode getNode(int index){
String str;
LinkedListNode prevnode = first.getNext();
for(int i=0;i<index-1;i++){
prevnode = prevnode.getNext(); // reaching the index node.
}
return prevnode;
}

// Swapping the Kth node from first and last alike.
public void specialSwap(int index){
LinkedListNode frontnode = first.getNext();
LinkedListNode lastnode = first.getNext();
frontnode = getNode(index); // obtain the first node
lastnode = getNode(size()-index+1); // obtain the last node

// Swap the Nodes values. no need of breaking the nodes.
String temp = frontnode.getName();
frontnode.setName(lastnode.getName());
lastnode.setName(temp);
}

#include<iostream>
using namespace std;

struct node{
	int data;
	node *next;
};

int main()
{
	
	node *list,*nptr,*tptr;
	int item,n,i;
	list=NULL;
	
	cout<<"PLEASE.......Type how many nodes that you want    ";
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cout<<"Type your "<<i<<" node item  ";
		cin>>item;
		nptr=new(node);
		nptr->data=item;
		nptr->next=NULL;
		if(list==NULL)
		{
			list=nptr;
			tptr=nptr;
		}
		else
		{
			tptr->next=nptr;
			tptr=nptr;
		}
	}
	tptr=list;
	for(i=1;i<=n;i++)
	{
		
		cout<<tptr->data<<"    ";
		tptr=tptr->next;
		
	}
	cout<<endl<<endl;
	
	int k,last,first;
	cout<<"input K for swapping the Kth node from the start with the Kth node from the last.......=";
	cin>>k;
	tptr=list;
	first=k-1;
	last=(n-k);
	int mid=(n-k+2);
	node *pptr,*sptr,*wptr=NULL,*temp2=NULL,*temp1=NULL;
	int count=1;
	tptr=list;
	for(i=1;i<=n;i++)
	{
		
		if(count==first)
		{
			pptr=tptr;
			temp2=pptr->next;
		}
		else if(count==last)
		{
			sptr=tptr;
			temp1=sptr->next;
			
		}
		else if(count==mid)
		{
			wptr=tptr;
			
		}
		tptr=tptr->next;
		count++;
		
		
	}
	int d;
	d=(n/2);
	if(d!=k)
	{
		
		temp1->next=pptr->next->next;
		
		
		pptr->next=temp1;
		
		
		
		sptr->next=temp2;
		
		
		temp2->next=wptr;
	}
	
	else 
	{
		pptr->next=temp1;
		temp1->next=sptr;
		sptr->next=wptr;
	}
	
	
	int g;
	
	for(g=1;g<=n;g++)
	{
		cout<<tptr->data<<"   ";
		tptr=tptr->next;
		
	}
	
    cout<<endl<<endl;
	
	return 0;
}

Algorithm:
1.Get the linked list lenghth. If it is less than 'K' print the error message. O(N)
2.Traverse to the 'K' the element from the beginning. O(N)
3.Traverse to the N-Kth element from the beginning. O(N)
4. Swap them.O(1)
5.End of Algorithm

Complexity:
O(N).