Google Interview Question: Reverse a linked list without... | Glassdoor.com.au

Interview Question

Software Engineer Interview

Reverse a linked list without using temporary variables.

Answer

Interview Answer

4 Answers

0

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

Interview Candidate on 29/10/2014
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 01/11/2014
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 05/11/2014
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 12/06/2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.