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