Amazon Interview Question
Software Engineer / DevelopersIf the length of linked list is odd, it is the same as reverse the whole linked list.
I use () to show alternative nodes
e.g. a (b) c (d) e (f) g --reverse--> g f e d c b a, same as reverse the whole list.
If the length of linked list is even, take two elements as a unit, it is same as reverse the linked list units.
e.g. a (b) c (d) e (f) --reverse--> e f c d a b
equivalent (ab)(cd)(ef) -- reverse -->(ef)(cd)(ab)
There are 3 basic steps as far as i can think
1. Split the main list into 2 lists - each list containing the alternate elements. Each time you add a node to the sublist, do a Push(node). This way the elements in the sublists will be in reverse order
eg: 1-2-3-4-5-6 is split into 2 lists 5-3-1 and 6-4-2
This can be done in O(n) time.
2. Now shuffle merge the 2 sublists, starting from first sublist. This can be done in O(n) time again.
5-6-3-4-1-2
Therefore time complexity is O(n) + O(n) = O(n)
i/p: [a] -> b -> [c] -> d -> [e] -> f
alternates nodes are one which are in [] brackets.
o/p: e -> b -> c -> d -> a -> f
my solution:
1) split the list into two different list.
alternate sub list => a->c->e->NULL and normal sub list => b->d->f->NULL
2) reverse alternate sub list. now you have
e->c->a->NULL; and b->d->f->NULL;
3) merge above sub lists node by node to get.
e -> b -> c -> d -> a -> f
all the above steps can be achieved in o(n).
I dont think 2 stacks work. We need 1 stack and 1 queue.
The nodes to be reversed go in the stack.Others go in the queue.
1 -> 2-> 3-> 4 -> 5 -> null
desired result:
5 -> 2 -> 3 -> 4 -> 1-> null
push(1);
enqueue(2);
push(3);
enqueue(4);
push(5);
then:
pop(5);
dequeue(2);
pop(3);
dequeue(4);
pop(1);
running time - O(n)
void swap(Node* parentQ, Node* Q, Node* parentR, Node* R) {
if(!parentQ) {
start = R;
} else {
parentQ->next = R;
}
if(!parentR) {
start = Q;
}else {
parentR->next = Q;
}
Node* temp = Q->next;
Q->next = R->next;
R->next = temp;
}
void alternateReverse() {
if(isEmpty()) {
cout<<"\nEMPTY LIST...";
return;
}
if(!start->next) {
cout<<"\nONLY ONE ELEMENT IN LIST...";
return;
}
Node *P = NULL, *Q = start, *R = start->next;
start = R;
while(R) {
swap(P,Q,Q,R);
P = Q;
Q = Q->next;
if(!Q)
return;
R = Q->next;
}
}
Cannot think of an optimal solution for this one. Here it goes, just describing the pseudo code. Think of this problem as if you are asked to reverse the alternate characters in a string (char array)
- sg December 19, 2008- Traverse the node in the list
+ Add it to an Array of nodes
- Get the Length of Array
- If Length is odd, Length = Length - 1 //since we start with 0, the last node to be reversed will be even
- for I = 0, J = Length; I <= ArrayLength/2 && J >= ArrayLength/2; I+=2, J-=2)
Swap (I&&J)