## Amazon Interview Question for Interns

Country: United States

Comment hidden because of low score. Click to expand.
3
of 3 vote

There can be various methods to reverse a linked list, but here we can take advantage of it being a doubly linked list:

1. loop from head to tail. For each node swap next and prev.

{
r=p->next;
p->next=p->next^p->prev;
p->prev=p->next^p->prev;
p->next=p->next^p->prev;
}

2.swap head and tail.

Comment hidden because of low score. Click to expand.
2
of 2 vote

Java:

``````public static Node reverse(Node head){
Node n = head, next;
while(n.next() != null){
next = n.next;
n.next = n.prev;
n.prev = next;
n = next;
}
// n is the new head.
return n;
}``````

Comment hidden because of low score. Click to expand.
0

I was unsure about "no extra space". I thought they meant strictly NO extra space (in which case you wouldn't be allowed to use the "next" variable to temporarily store a value... no wonder I was stuck for so long.

Comment hidden because of low score. Click to expand.
0

your code will not swap the next and prev values of the last node. In such a case your while condition will change. or after the while loop you need to swp yr next and prev of the newly found head node.

Comment hidden because of low score. Click to expand.
0

I was wondering if you can explain step by step how and what each part of the code works? Prepping for an incoming interview.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Reversing doubly linked list is easier than SLL. Just reverse head and tail of each node of DLL.

Comment hidden because of low score. Click to expand.
0

and swap the prev and next pointers :)

Comment hidden because of low score. Click to expand.
1
of 1 vote

{

if(node.nxt==null)
return;
else
{

Node tmp=node.prev;
node.prev=node.next;
node.next=tmp
}
---Ajeya

Comment hidden because of low score. Click to expand.
0
of 0 vote

Node prev=null;
while(temp!=null){
Node temp1=temp.next;
temp.next=prev;
prev=temp;
temp=temp1;

}
return prev;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

There are two ways to do the problem :
(1) to keep swapping the data of first and last node - O(n/2) - extra space not required
(2) to swap the next n prev pointers for each node. - O(n) - extra space required for swapping (= size of node)

Please feel free to comment and point out any possible mistake on above approches.

Comment hidden because of low score. Click to expand.
0

Regarding first approach. You've got to traverse half the list from both head and tail, meaning that you will have traversed the entire list. Therefore O(n), not O(n/2).

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````ListNode *reverse(ListNode* head)
{
if(head == NULL || head->next == NULL)
ListNode *p = head;
while(p->next != NULL)
{
ListNode *temp = p->next;
p->next = p->prev;
p->prev = temp;
p = temp;
}
p->next = p->prev;
p->prev = NULL;
return p;
}``````

Comment hidden because of low score. Click to expand.
0

Sorry, did not notice the requirement "not use additional space".

``````ListNode *reverse(ListNode* head)
{
if(head == NULL || head->next == NULL)
ListNode *p = head;
while(p->next != NULL)
{
p->next = p->next ^ p->pre;
p->pre = p->next ^ p->pre;
p->next = p->next ^ p->pre;
p = p->pre;
}
p->next = p->prev;
p->prev = NULL;
return p;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the emphasis on the question is more on "not use additional space", so all the algos using Next or any other temporary variable is not accepted.

In c++, all these pointers are anyways long, so you can do this to swap 2 pointers without using a temporary variable:

n1= (Node *) ((long)n1+ (long)n2);
n2 = (Node *) ((long)n1- (long)n2);
n1= (Node *) ((long)n1- (long)n2);

Comment hidden because of low score. Click to expand.
0
of 0 vote

Find and return the tail, the list is reversed because it is a double linked list.

Use two pointers, p1 and p2. p1 move 1 step forward, p2 move 2 stop forward, when p2 return back to head, p1 will be the tail.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void reverse(node ** headRef)
{
node* previousNode = NULL;
node* curr = *headRef;
while(curr)
{
curr->prev = curr->next;
curr->next = previousNode;
previousNode = curr;
curr=curr->prev;
if (curr == NULL)
{
break;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Most of you are not checking error conditions.
Try it with a list of length 1. Some of the above solutions I've seen will actually return null for the new head.

``````static DoublyLinkedNode reverse(DoublyLinkedNode head) {

while (head.next != null) {

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why cant i swap just the data i the head and tail ??

do i really need to do all the pointer manipulations in a doubly linked list ??

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why cant i just swap the data elements present in the first and the last node ??

I know that people might think that what if the no of variables in the Node of the list is O(n). in that case it might not be a viable option to swap data.. but if the node has constant no of data variables then its better we just swap the data.

suggestions welcomed.

Comment hidden because of low score. Click to expand.
0
of 0 vote

void reverse(){
node *temp=first,*temp2=first;
while(temp!=NULL){
swap(temp->next,temp->prev);
temp=temp->prev;}
swap(first,last);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

void reverse(){
node *temp=first;
while(temp!=NULL){
swap(temp->next,temp->prev);
temp=temp->prev;}
swap(first,last);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

void reverse(node **head,node **tail,int item)
{ node *loc;
{
}
while(loc!=item)
{
printf("%d",loc->info);
loc->next=loc->pre;
}loc->pre=loc->pre->next;
loc->pre->next=null;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

C:

``````void reverse(node **head)
{
node *prev = NULL;
while (NULL != *head) {
node *next = (*head)->next;
}
}``````

or:

``````void reverse(node **head)
{
node *new_head = NULL;
while (NULL != *head) {
node *elem = *head;
}
}``````

Java:

``````public static Node reverse(Node head) {
Node prev = null;
while (head != null) {
Node next = head.next;
}
return prev;
}``````

or:

``````public static Node reverse(Node head) {
Node newHead = null;
while (head != null) {
Node elem = head;
}
}``````

Note that above solutions can be easily transformed into recursive ones.

Comment hidden because of low score. Click to expand.
0

But what u hav tried to reverse is singly linked list. not doubly linked. Am i crcrt...............?

Comment hidden because of low score. Click to expand.
0

Yep, my bad. Didn't read it too carefully.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

its a double linked list..so just swap the head and tail.

Name:

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

### Books

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

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