Amazon Interview Question
InternsCountry: United States
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;
}
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.
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.
Reversing doubly linked list is easier than SLL. Just reverse head and tail of each node of DLL.
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.
ListNode *reverse(ListNode* head)
{
if(head == NULL || head->next == NULL)
return head;
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;
}
Sorry, did not notice the requirement "not use additional space".
ListNode *reverse(ListNode* head)
{
if(head == NULL || head->next == NULL)
return head;
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;
}
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);
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) {
DoublyLinkedNode tmpNext = head.prev;
head.prev = head.next;
head.next = tmpNext;
head = head.prev;
}
head.next = head.prev;
head.prev = null;
return head;
}
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.
void reverse(node **head,node **tail,int item)
{ node *loc;
item=*head->info;
while(*head->next!=null)
{
printf("%d",*head->info);
*head=*head->next;
*head->next=*head->next->pre;
}
loc=*head->next;
while(loc!=item)
{
printf("%d",loc->info);
loc->next=loc->pre;
}loc->pre=loc->pre->next;
loc->pre->next=null;
}
http://www.teamten.com/lawrence/writings/reverse_a_linked_list.html
C:
void reverse(node **head)
{
node *prev = NULL;
while (NULL != *head) {
node *next = (*head)->next;
(*head)->next = prev;
prev = *head;
*head = next;
}
*head = prev;
}
or:
void reverse(node **head)
{
node *new_head = NULL;
while (NULL != *head) {
node *elem = *head;
*head = (*head)->next;
elem->next = new_head;
new_head = elem;
}
*head = new_head;
}
Java:
public static Node reverse(Node head) {
Node prev = null;
while (head != null) {
Node next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
or:
public static Node reverse(Node head) {
Node newHead = null;
while (head != null) {
Node elem = head;
head = head.next;
elem.next = newHead;
newHead = elem;
}
return newHead;
}
Note that above solutions can be easily transformed into recursive ones.
But what u hav tried to reverse is singly linked list. not doubly linked. Am i crcrt...............?
There can be various methods to reverse a linked list, but here we can take advantage of it being a doubly linked list:
- Anonymous August 10, 20131. loop from head to tail. For each node swap next and prev.
for(p = head;p!=NULL;p=r)
{
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.