Interview Question

Software Engineer Interview

-

Google

Reverse a linked list without using temporary variables.

AnswerAdd Tags

Interview Answers

5 Answers

0

I was nervous and didn't answer it well. I should have done better if I calmed down a little.

Anonymous on

0

public static void ReverseNode(Node n) { if (n.Next == null || n.Next == n) return; ReverseNode(n.Next) n.Next.Next = n n.Next = null }

Anonymous on

0

pair reverse(Node* current){ if (current->next == NULL) return make_pair(current, current); auto result = reverse(current->next); result.second->next = current; current->next = NULL; return make_pair(result.first, current); }

Time cost should be O(N) on

0

Steve L. : Clever, but the question didn't specify a linked list of positive integers…but that trick, I _think_, could be used for the pointers in a language that used them.

Empty Set on

2

The above doesn't work since n will be pointing at the last element in the end. It should still point at the start. This should work: void reverse(Node lis) { if (lis == null) { return; } if (lis.next == null) { return; } reverse(lis.next); while (lis.next != null) { lis.val = lis.val ^ lis.next.val; lis.next.val = lis.val ^ lis.next.val; lis.val = lis.val ^ lis.next.val; lis = lis.next; } }

Steve L. on

Add Answers or Comments

To comment on this, Sign In or Sign Up.