Amazon Interview Question
Applications DevelopersCountry: India
Interview Type: Written Test
///recursive reverse will work
reverse(Node* node)
{
if (node == NULL) return;
if (node->next == NULL)
{
head = node;
return;
}
reverse(node->next);
node->next->next = node;
node->next = null;
}
I'm guessing that accessing the pointers that make up the linked list (node->next->next..) doesn't count toward the 'one pointer' we can use. If this assumption is correct, 'head' is the one pointer in this solution.
It uses an O(n) stack secretly.
And on this stack there are n pointer objects.
The question is dumb.
Here is a tail recursive solution using one pointer. O(n):
public static LinkedList reverse(LinkedList head, LinkedList reversed){
if(head==null) return reversed;
LinkedList current = new LinkedList();
current = head;
head = head.next;
current->next = reversed;
return reverse(head, current);
}
A good coder may get irritated when he sees this type of purposeless questions, Wont even waste my time even trying it.
List* reverse_list(List* head)
{
List* current = head;
List* result = NULL;
while(current != NULL)
{
List* next = current->next;
current->next = result;
result = current;
current = next;
}
return result;
}
I got this solution from one of the blogspot sites. Unfortunately I am not able to paste link here.
I think, this makes some sense. But if you consider result as a separate pointer storage. This uses two pointers but without any additional storage.
I feel takes o(n)
Is this correct?
This solution uses 3 pointers - current, result and next. It is as good as using next, previous and current (in fact, the same approach). Although it works fine, it doesn't fulfill the "1 pointer" criteria of the question.
List* reverse_list(List* head)
{
List* current = head;
List* result = NULL;
while(current != NULL)
{
List* next = current->next;
current->next = result;
result = current;
current = next;
}
return result;
}
This code looks good to me but it uses two pointers (considering result as a pointer) and it doesnt use any additional storage.
I found it in one of the blogspot site.
It takes O(n). Is this correct?
recursion( List *node)
{
Node *p;
if(node->next != NULL)
p = recursion(node->next);
else
return node;
p->next = node;
return node;
}
typedef struct Node {
int val;
Node *next;
}*Node;
void swap(Node *a, Node *b);
void reverselist(Node *head) {
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
while (head <= temp) {
swap(head++, temp--);
}
}
void swap(Node *a, Node *b) {
a->val = a->val ^ b->val;
b->val = a->val ^ b->val;
a->val = a->val ^ b->val;
}
Hi there my version with 1 pointer in java looks as follows (I do assume head is given from the reversed list structure)
public void reverse() {
reverse(head).next = null;
}
private Node reverse(Node current) {
if (current.next == null) {//last node
head = current;
return current;
} else {
reverse(current.next).next = current;
}
return current;
}
void reverse_single_pointer(node **head)
{
node *newone = NULL;
while(*head)
{
(*head)->link = (node*)((int)(*head)->link ^ (int)(newone));
newone = (node*)((int)(*head)->link ^ (int)(newone));
(*head)->link = (node*)((int)(*head)->link ^ (int)(newone));
*head = (node*)((int)(*head) ^ (int)(newone));
newone = (node*)((int)(*head) ^ (int)(newone));
*head = (node*)((int)(*head) ^ (int)(newone));
}
*head = newone;
}
could be a trick question.
Instead of extra pointer, declare extra int, and keep casting it back and forth.
+1 for solution.
No idea, if Amazon still ask these types of questions. May be there will be other additional constraints or conditions.
Not sure if this can be a solution but here is the code, seems I am using 1 pointer:
static Node<Integer> reverseList(Node<Integer> node) {
Node<Integer> last = node;
while (last.getNext() != null) {
last = last.getNext();
}
while (node != last) {
if (last.getNext() == null) {
last.setNext(node);
node = node.getNext();
last.getNext().setNext(null);
}
else {
Node<Integer> temp = last.getNext();
last.setNext(node);
node = node.getNext();
last.getNext().setNext(temp);
}
}
return node;
}
/**
* algorithm to reverse a singly linked list using one pointer
* without any additional datastructures
* @author ksjeyabarani
*
*/
public class ReverseSingleLinkedList {
public static void main(String[] args) {
ReverseSingleLinkedList r = new ReverseSingleLinkedList();
LList<Integer> l = new LList<Integer>();
l.add(1);
l.add(2);
l.add(3);
l.add(4);
System.out.println("List is " + l);
l.reverse();
System.out.println("List after 2 pointer reverse " + l);
l.reverse();
System.out.println("List reversed back to original " + l);
l.reverseWithOnePointerAndNoExtraDS();
System.out.println("List WithOnePointerAndNoExtraDS " + l);
}
private static class LList<T> {
Node<T> head;
private int size;
public void add(T data) {
Node<T> n = new Node<T>(data);
if(null == head) {
head = n;
} else {
Node<T> x = head;
while(x.next != null) {
x = x.next;
}
x.next = n;
}
size++;
}
// uses three pointers - can be improved to use two pointers by accessing third node using two.next
public void reverse() {
if((null == head) || (head.next == null)) {
return;
}
Node<T> one = head;
Node<T> two = one.next;
Node<T> three = two.next;
head.next = null;
while(two != null) {
two.next = one;
one = two;
two = three;
if( null != two) {
three = two.next;
}
}
head = one;
}
public void reverseWithOnePointerAndNoExtraDS() {
if((null == head) || (head.next == null)) {
return;
}
int mid = size/2;
int x = 0;
while (x < mid) {
T temp;
temp = get(x).data;
get(x).data = get((size-1)-x).data;
get((size-1)-x).data = temp;
x++;
}
}
public Node<T> get(int index) {
if((index >= size) || (index < 0)) {
return null;
}
Node<T> n = head;
for(int x = 0; x<index; x++) {
n = n.next;
}
return n;
}
public String toString() {
if(null == head)
return null;
StringBuilder sb = new StringBuilder();
Node<T> x = head;
while(x != null) {
sb.append(x.data + " ");
x = x.next;
}
return sb.toString();
}
private static class Node<T> {
T data;
Node<T> next;
public Node(T data) {
this.data = data;
}
@Override
public String toString() {
return data + " ";
}
}
}
}
public void reverse(){
if(head != null){
/*
* A -> B -> C -> D -> E -> F
* F -> E -> D -> C -> B -> A
*/
Node nextNode = head.getNext(); //B
//set head's next to null
head.next = null;
while(nextNode != null){
Node currentNextNode = nextNode.getNext(); //C
// set the nextNode to head
nextNode.setNext(head); //B --> A
// B is tempHead node now
head = nextNode;// (head)B --> A
//get original next to B
nextNode = currentNextNode;
}
}
}
Its easy, you just store the XOR of the previous pointer and the next pointer in the pointer part of the LinkedList Node and then just extract the Node's next pointer or the previous pointer whenever required by using one of the prev/next pointers. You keep doing this and storing the XOR instead of just the next pointer and you can reverse the linked list using only one pointer.
Syntax might be a little off, haven't done Java in a while
- Interviews Suck November 03, 2013