## Amazon Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Written Test

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

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.

@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

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.

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

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!

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

instead of "ptr3->next!=NULL".

Hey, Anon! Thanks for your code!

@sushmita Sorry to see people being treated like this. Try to follow the code for actual examples to convince yourself if it works for the general case.

@AbbySol I don't know what kind of bug you have in your social programming, but I don't know how you construed her asking for clarification as being overly critical.

As for the code: if you know the second pointer is going to have "head" as its initial value (once you start using it), why don't you just assign that value to it after its declaration? Also, I don't see a need for the if-conditional checking the pointers for NULL, because you have already done so in the while loop. I am assuming that those pointers are not meant to refer to memory concurrently accessed as we swap or this implementation would have other issues to worry about.

It seems like the following would be a functionally equivalent implementation:

```
node *n = head, *nx, *ny = head;
int p;
for (p = 0; n != NULL; ++p, n = n->next) {
if (p == k) nx = p;
if (p > k) ny = ny->next;
}
if (p <= k) return null;
auto temp = nx->data;
nx->data = ny->data;
ny->data = temp;
return head;
```

I also changed the int to auto, because it looks a bit more general.

However, I have the same concern with this question as @vik above: if the linked list owns the contents of the nodes, copying contents may be permissible. With a general purpose container, that is usually not acceptable. The caller is most likely owning the objects they inserted and has references to them. If we swap out data like this, the external references will suddenly refer to different objects.

Imagine, for example that each item in the linked list is a "car" object. Each car has an owner which holds a pointer to the car they own. The linked list is the order in which the cars are serviced at a car dealership. If you swap and copy car objects like that you end up with the cars in the new positions, but owners suddenly end up owning different cars than before.

There are other issues with this, such as assuming that it's okay to copy objects like that. Many examples preclude this. It is one of the reasons why it's a bad idea to put std::auto_ptr<T> instances into an STL container. Copying such an instance transfers ownership of the pointer being wrapped and an std::sort(...) could create copies and lose ownership that way.

I will follow up with another post in a second for a solution swapping the pointers.

So, I haven't tested this code, yet. I'm pretty tired and going to hit the sack now, but it should outline the steps.

```
node* swap_k(node* head, int k) {
node *pn, *n = head,
*pnx, *nx,
*pny, *ny = head;
int p;
for (p = 0; n != NULL; ++p) {
pn = n;
if (p == k) {
pnx = pn;
nx = n;
}
if (p > k) {
pny = ny;
ny = ny->next;
}
n = n->next;
}
if (p <= k) return NULL;
if (nx == ny) return head;
// Head and tail are to be swapped, so update head.
if (p == 0) {
ny->next = nx->next;
pny->next = nx;
nx->next = NULL;
head = ny;
// Adjacent nodes are to be swapped.
} else if (p / 2 == k + 1) {
pnx->next = ny;
auto tmp = ny->next;
ny->next = nx;
nx->next = tmp;
// Nodes are at least one apart.
} else {
pnx->next = ny;
auto tmp = ny->next;
ny->next = nx->next;
pny->next = nx;
nx->next = tmp;
}
return head;
}
```

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

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

Have you tested this code for the case that the first and last node are to be swapped and the list contains two nodes, i.e. nodes are adjacent AND the head needs to be updated? Sorry for not having tried this myself. If I don't hear from you, I will compile your code and try myself tomorrow.

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.

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

}

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

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

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

}

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

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

}

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

}

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

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

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

}

}

}

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

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

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

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

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

}

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

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

}

}

This can be solved using the Runner Technique.

Let n1, n2, and n3 be Node variables. Let n1 and n2 = head. Iterate n1 K nodes down the list. If n1.next is null before you have completed the traversal, the list is smaller than K. Once you have iterated K nodes, let n3 = n1. Traverse both n1 and n2 until the n1 is at the end of the list. At this point, n3 is pointing at the Kth node from the head, and n2 is pointing at the Kth node from the tail. Swap the data and you're done.

```
void swap(Node head, int k) {
if (head == null) return null; // list is empty
Node<T> n1, n2, n3;
n1 = head;
n2 = head;
// find the Kth node from the head, if possible. return null, otherwise.
for (int i = 0; i < k; i++) {
// check that k is not larger than list size
if (n1.next == null) {
System.out.println("List is of lesser size!");
return null;
}
n1 = n1.next;
}
n3 = n1;
// find the Kth node from the tail
while (n1.next != null) {
n1 = n1.next;
n2 = n2.next;
}
// do the swap
T tmp = n2.data;
n2.data = n3.data;
n3.data = tmp;
}
```

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

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

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

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.

- Anonymous May 20, 2012