Amazon Interview Question Software Engineer / Developers


Country: India
Interview Type: Written Test


Comment hidden because of low score. Click to expand.
18
of 22 vote

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;

- Anonymous on May 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

But this code is only applicable when k=3 and n=10 and not for the general case.

- sushmita on June 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can this possible less than O(n)

- Subhransu on June 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sushmita, it's a general and good solution!

- Avenger on June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But this is not a generic solution and will not be fit for PROJECT's.
Let's say i have pass unknowingly a circular list to your written function. Will it works in that case? also if the list is having a loop then how will you handle it?

- subrata on July 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@subrata
If a list is circular or it contain a loop, then what is the last node of this link list?
There would be none.
And so the question becomes invalid.
Therefore the question is only for singly linked list that do not contain any loops, and therefore the answer is good.

- Kuldip on July 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sushmita: it works for all value of k and n..
@Subhransu: no it is nt possible to obtain order less than n, as we hv to scan the list atleast once in order to find kth element from the end. If we know the no. of nodes n in linked list in advance, only then it is possbl to obtain order less than n

- Aditya Goel on July 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i m not sure if the code works for all cases. For example let n=10 and k=8. In such case 2nd node is the 8th element from the end. But you dont know the number of elements(n=10) at the beginning.

- enigma on August 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sushmita - based on your response its clear your a critic and your an idiot

- AbbySol on August 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"Your an idiot". LOL!

- Anonymous on September 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think it will work but there is a small issue ...you are swapping the data(or its pointer) instead of changing a pointer itself...And in almost all the cases the answer is not acceptable
For example
Assume that the node consists of object or data pointers to more than one data... in that case you are supposed to rearrange the nodes using the pointers rather than swapping the data(or its ptrs) [this is what my interviewer said to me at interview at MS and which seems fair enough]

So similar thing can be achieved by just rearranging next pointers leaving data untouched (obviously i will have to save the pointers to the elements prev to the elements to be swapped)

Following is the c++ code

node* swapkthFirstAndLast(node* head,int k){
    if (head==NULL||k<=0 )return head;
    int i(k);
    node * curr(head), *startPrev(NULL), *startEle(NULL),*tmp(NULL),*prev(NULL), *currBack(head);
    while ((i-1)>0 && curr->next){
        prev = curr;
        curr = curr->next;
        i--;
    }
    if ((i-1)>0){
        cout<<"Invalid value of K"<<endl;
        return head;
    }
    startEle = curr;
    startPrev = prev;
    while(curr->next){
        prev = currBack;
        currBack = currBack->next;
        curr =  curr->next;
    }
    //same elements
    if (currBack == startEle)
        return head;
    //end elements
    if (k==1){
        currBack->next = head->next;
        prev->next = head;
        head->next = NULL;
        head = currBack;
        return head;
    }
    //adjacent 
    if (currBack->next==startEle){
        tmp = startEle->next;
        startEle->next=currBack;
        currBack->next=tmp;
        prev->next= startEle;
        return head;
    }
    //lying elsewhere
    prev->next =  startEle;
    tmp= startEle->next;
    startEle->next=currBack->next;
    currBack->next = tmp;
    startPrev->next = currBack;
    return head;
}

i had tested on k = -ve, 0,1,2,3...,>len(list) on both even and odd lengths and hence covering all four cases mentioned by @Shondik ...but if i still missed any corner case let me know

- vik on February 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this code doesn't work correctly. When i tried to swap element #2 its swap 2nd from begin and 3rd from end!
And this last code example working perfect!

- stetsyk.yaroslav on June 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it works correctly....but there is a little change in while loop..it will be "ptr3!=NULL"
instead of "ptr3->next!=NULL".

- rahul singh on July 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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

- Aashish on July 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Shondik,

You have written very beautiful code handling all cases.
But I think there is a possible of t2 and t4 hold NULL values.. which you have not handled. please correct me if I am worng :)

- Vignesh on October 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- rai.kaushal on May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
}

- MN on May 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

awesome...

- Buzz Aldrin on October 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- Pavan Dittakavi on May 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

3 is not necessary, carry on traverse from 2 by another total-2k+1.

- zaq123321 on June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- VillageMonkey on May 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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;
}

- Anonymous on May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't handle the case when nodes to be swapped are adjacent.

- Aashish on July 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- bugbug on May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- bugbug on May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- bugbug on May 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Vibhanshu jha on May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Ramachandran on May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Ramachandran on May 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

        }
    }
}

- AJ on May 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

}

- Ahmed on May 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think your code will not work when number of element in the list is 7 and let K be the 6. It will give segmentation Fault. 
Correct me if if i am wrong.
Thanks

- Pranay Singhania on May 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

}

- Anonymous on May 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
  }
}

- Deepak Garg on May 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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..

- Prem on May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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..

- Prem on May 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*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;
}

- neelabhsingh100 on May 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- grenyaz on May 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- yomero on May 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- hmonfared on May 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- hmonfared on May 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- hmonfared on May 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- hmonfared on May 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- hmonfared on May 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- hmonfared on May 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you can just reverse the value.

- ping on May 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- hairsh on May 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- NK on June 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Aditya Saripalli on June 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous on June 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes
- KKR on June 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Aditya Saripalli on June 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

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");
		}

}

- slash on June 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Brilliant!!!! ROFL!!!!

- Kashif Khan on August 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);


}

- Anonymous on June 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please comment on the above code if you have any doubt..and also find the whole linked program for the same...

package linkedlists;

public class LinkedList {
	
	Node HEAD;
	
	public Node getHEAD() {
		return HEAD;
	}

	public void setHEAD(Node hEAD) {
		HEAD = hEAD;
	}

	public Node getTAIL() {
		return TAIL;
	}

	public void setTAIL(Node tAIL) {
		TAIL = tAIL;
	}

	Node TAIL;
	
	public LinkedList(Node HEAD,Node TAIL) {
		this.HEAD = HEAD;
		this.TAIL = TAIL;
	}

	public void traveseList(){
		Node n = this.HEAD;
		
		while(n != null){
			System.out.println("Value at Node::" + n.getKey());
			n = n.getNext();
		}
	}
	
	public void reverseList(){
		
		Node n,n1,n2;
		n =  this.HEAD;
		n1 = n.getNext();
		n2 = n1.getNext();
		this.TAIL = n;	
		n.setNext(null);
		while(n1.getNext() != null){
			n1.setNext(n);
			n = n1;
			n1 = n2;
			n2 = n2.getNext();
		}
		n1.setNext(n);
		this.HEAD = n1;
	}
	
	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);
		
		this.traveseList();
		
	}
	
	public static void main(String[] args) {
		
		Node n1 = new Node();
		Node n2 = new Node();
		Node n3 = new Node();
		Node n4 = new Node();
		Node n5 = new Node();
		Node n6 = new Node();
		
			n1.setKey("JAVA");
			n2.setKey("RUBY");
			n3.setKey("HTML");
			n4.setKey("C++");
			n5.setKey("C");
			n6.setKey("Obj C");
			
			n1.setNext(n2);
			n2.setNext(n3);
			n3.setNext(n4);
			n4.setNext(n5);
			n5.setNext(n6);
			n6.setNext(null);
			
			LinkedList list = new LinkedList(n1, n6);
			list.traveseList();
			list.reverseList();
			System.out.println("Revers List...");
			list.traveseList();
			list.replaceKthCharacter(3);
	}
}

- KKR on June 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Mahesh Deo on July 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- AJ on July 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)


}

- invincibleveer on July 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// (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;
}

- Dennis B. on July 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
     }
  }

- ritika on July 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}

- uma trika on August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Al on August 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- ShoebBhaldar on October 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- venkat on October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");

}

- mandeep624 on November 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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()
{
	
}*/
	   	
}

- PK on November 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- pradeep on January 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()

- Sandy on April 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- vrajendra.singh.mandloi on April 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- MD. Ashik Adnan on May 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void mainwork()
 {
//initialise to start.
//count is the length of link list
//n is the position at which swap needs to be made.
 temp=p;
 int count=0;
 while(temp!=NULL)
 {
 count++;
 temp=temp->link;
 }
 int n=4;
 prev=p;
 curr=prev->link;
 next=curr->link;
 for(int i=0;i<n-1;i++)
 {
  prev=prev->link;
  curr=curr->link;
  next=next->link;
 }
 prev1=p;
 curr1=prev1->link;
 next1=curr1->link;
 for(i=0;i<count-n-1;i++)
 {
  prev1=prev1->link;
  curr1=curr1->link;
  next1=next1->link;
 }
 //cout<<"\n"<<curr->data<<","<<curr1->data;

 if(n<count/2)
 {
 prev->link=curr1;
 curr1->link=next;
 prev1->link=curr;
 curr->link=next1;
 }
else
{

cout<<"Cant perform this operation";

}




 }

- Anonymous on July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<malloc.h>

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

int append(struct node **q,int num) {
	struct node *temp, *r;
	temp = *q;
	if(temp == NULL) {
		temp = (struct node *) malloc(sizeof(struct node));
		temp->data = num;
		temp->link = NULL;
		*q = temp;
		return 0;
	}
	while(temp->link != NULL)
		temp = temp->link;
	r = (struct node *) malloc(sizeof(struct node));
	r->data = num;
	temp->link = r;
	return 0;
}

int display(struct node *q) {
	struct node *temp = q;
	while(temp != NULL) {
		printf("data = %d\n",temp->data);
		temp = temp->link;
	}
	return 0;
}

int sizeofl(struct node *temp) {
	int count = 0;
	struct node *temp1 = temp;
	while(temp1 != NULL) {
		count++;
		temp1 = temp1->link;
	}
	return count;
}

int swap_list(struct node **q,int position) {
	struct node *temp = *q, *ptr1 = *q,*ptr2 = *q;
	int size_list,i,temp_data = 0;
	size_list = sizeofl(temp);
	printf("count = %d\n",size_list);
	for(i=1; i<position;i++)
		ptr1 = ptr1->link;
	printf("ptr1 data = %d\n",ptr1->data);
	for(i=0;i<size_list- position;i++)
		ptr2 = ptr2->link;
	printf("ptr1 data = %d\n",ptr2->data);
	temp_data = ptr1->data;
	ptr1->data = ptr2->data;
	ptr2->data = temp_data;
	return 0;
}

int main()
{
	struct node *k = NULL;
	append(&k,1);
	append(&k,2);
	append(&k,3);
	append(&k,4);
	append(&k,5);
	append(&k,6);
	append(&k,7);
	append(&k,8);
	append(&k,9);
	display(k);
	swap_list(&k,3);
	display(k);
	return 0;
}

- agmegharaj on November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void swap(struct node *node1,struct node *node2)
{
if(node1 == NULL || node2 == NULL)
{
cout<<"LIST IS OF LESSER SIZE"<<endl;
return;
}
int temp_data = 0;
temp_data = node1->data;
node1->data = node2->data;
node2->data = temp_data;
struct node *temp = start;
while(temp->next != NULL)
{
cout<<temp->data<<"->";
temp = temp->next;
}
cout<<temp->data<<endl;
}

void trav_swap(int K)
{
int curr = 1;
struct node *temp = start;
struct node * node1 = NULL, *node2 = NULL;
if(K == 0)
{
cout<<"INVALID INPUT"<<endl;
return;
}
while(temp != NULL && curr != K)
{
temp = temp->next;
curr++;
}
if(curr == K)
{
node1 = temp;
node2 = start;
while(temp->next != NULL)
{
temp = temp->next;
node2 = node2->next;
}
}
swap(node1,node2);

}

- anonymous on December 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void swap(struct node *node1,struct node *node2)
{
    if(node1 == NULL || node2 == NULL)
    {
      cout<<"LIST IS OF LESSER SIZE"<<endl;
      return;
    }
    int temp_data = 0;
    temp_data = node1->data;
    node1->data = node2->data;
    node2->data = temp_data;
    struct node *temp = start;
    while(temp->next != NULL)
    {
       cout<<temp->data<<"->";
       temp = temp->next;
    }
    cout<<temp->data<<endl;
}

void trav_swap(int K)
{
    int curr = 1; 
    struct node *temp = start;
    struct node * node1 = NULL, *node2 = NULL;
    if(K == 0)
    {
      cout<<"INVALID INPUT"<<endl;
      return;
    }
    while(temp != NULL && curr != K)
    {
               temp = temp->next;
               curr++;
    }
    if(curr == K)
    {
        node1 = temp;
        node2 = start;
        while(temp->next != NULL)
        {
           temp = temp->next;
           node2 = node2->next;
        }
    }
    swap(node1,node2);
    
}

- rashi on December 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use double linked list &
two pointers,one from first till our k value
and another from last till our k value then exchange the values

- vineel on December 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

check skillgun.com for free online tests with java interview questions

- anishrushi on March 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void sortlist (int index)
{
Node temp=new Node ();
Node temp2=Head;
Node current=Head;
int count=0;

for (current=Head;current!=null;current=current.next)
{
count++;
if (count==index)
{
temp=current;
}
}
if (index>count)
{
System.out.println("LIST IS OF LESSER SIZE");
}

else
{
for (int j=0;j<(count-index);j++)
{
temp2=temp2.next;
}


int e1=temp.item;
Node temp3=temp;
System.out.println(temp3.item);
temp=temp2;
//temp.item=temp2.item;
temp2=temp3;;
}
}

- Ashi on July 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

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).

- Pavan Dittakavi on May 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Step 3 : Traverse to the N-K+1 th element from the beginning to get the kth element from last

- Nitin Gupta on May 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Logic is good if nitingupta's statement is consider

- prince on May 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Nitin and Prince I think Traversing till N-K is correct..

but for 2) Traverse to the ('K'-1) the element from the beginning Because we need to swap Nodes not just values..

Hope you got my point.

- User on May 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Nitin and Prince I think Traversing till N-K is correct..

but for 2) Traverse to the ('K'-1) the element from the beginning Because we need to swap Nodes not just values..

Hope you got my point.

- User on May 18, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More