## Amazon Interview Question

**Country:**United States

public static Node transformList(Node head, int n){

Node temp1, temp2, midNode=null;

Node start = head;

temp1 = head;

for(int i=0; i<n/2-1; i++){

midNode = temp1.getNext();

temp1 = midNode;

}

Node swapIndex = reverseList(midNode.getNext());

System.out.println("swap is "+swapIndex.data);

midNode.setNext(null);

return mergeList(head, swapIndex);

}

```
public void transform(SingleLLNode header) {
int count = 0;
SingleLLNode current = header;
while(current != null) {
count++;
current = current.next;
}
int start = count/2,iteration = 1;
while(start > 1) {
int i = 0;
current = header;
while(i< start) {
current = current.next;
i++;
}
i = 0;
while (i < iteration) {
int temp = current.data;
current.data = current.next.data;
current.next.data = temp;
i++;
current = current.next.next;
}
iteration++;
start--;
}
}
```

```
class Link {
public String data;
public Link next;
Link() {
}
public Link(String data) {
this.data = data;
}
}
class InsertLinkList {
private Link first;
InsertLinkList() {
first = null;
}
public void intializeLink(String data) {
Link a = new Link(data);
if (first == null) {
first = a;
a.next = null;
} else {
a.next = first;
first = a;
}
}
public void display(InsertLinkList lin) {
while (first != null) {
System.out.println(first.data);
first = first.next;
}
}
public void display1(InsertLinkList lin) {
Link first1 = first;
Link first3 = first;
while (first1.next != null) {
System.out.println(first3.data);
first1 = first3.next.next.next;
System.out.println(first1.data);
first3 = first3.next;
}
}
}
public class LinkedLista1b1a2b2 {
public static void main(String[] args) {
InsertLinkList lin = new InsertLinkList();
lin.intializeLink("b3");
lin.intializeLink("b2");
lin.intializeLink("b1");
lin.intializeLink("a3");
lin.intializeLink("a2");
lin.intializeLink("a1");
lin.display1(lin);
}
}
```

Node rearrange(Node head, Node b1)

{

Node p1 = head;

Node p2,p2_start = head;

if (head == null)

return;

while(p1 != b1)

p2 = p2.next;

Node p1_end = p2;

while(p1!=p2_start && p2!=null)

{

Node t1 = p1.next;

Node t2 = p2;

if (t2!=null)

p1.next = t2;

else //if number of b < number of a

{

p1_end = null;

return head;

}

if (t1!=p2_start)

{

p1.next.next = t1;

p1 = p1.next.next;

p2 = p2.next;

}

else //if number of a < number of b

{

p1.next = p2;

return head;

}

}

return head;

}

```
/* This code works for any no of nodes */
alternate(struct list *a)
{
struct list mid,temp,*fptr=a,*sptr=a;
int i =0;
/* find the middle of the list */
while(fptr->next != NULL)
{
if(i==0)
{
fptr=fptr->next;
i=1;
}else
{
fptr=fptr->next;
sptr=sptr->next;
i=0;
}
}
fptr = a;
temp = fptr->next;
mid = sptr;
/* Now sptr in the middle of the list and fptr start of the list */
while(sptr)
{
if (sptr == fptr || sptr == temp)
break;
fptr->next = sptr;
sptr = sptr->next;
fptr = fptr->next;
if (!sptr || temp == mid)
break;
fptr->next = temp;
temp = temp->next;
fptr = fptr->next;
}
if(sptr)
fptr->next = sptr;
}
Time Complexity : O(n) Space Complexity : O(1)
Same can be achieved by Dynamic programming but takes O(nlog(n))
```

- struggler February 23, 2014