Reverse a single linked list.

Question

Utilisateur anonyme · Accepted Answer

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

donutello · Answer

Candidate: Using a stack would make it O(n) space. The optimal solution uses O(1) space.

Anonymous: Your answer will always return NULL because your exit condition is for head == null and then you return head.

I don't think the below is optimal - feels like I should be able to eliminate at least one variable:
void reverseList(Node **ppHead)
{
    ASSERT(ppHead != NULL);
    if(!ppHead)
    {
        return;
    }

    Node *pPrev = NULL;
    Node *pCur = *ppHead;
    while(pCur)
    {
        Node *pNext = pCur->pNext;
        pCur->pNext = pPrev;
        pPrev = pCur;
        pCur = pNext;
    }
    *ppHead = pCur;
}

Utilisateur anonyme · Answer

There are multiple ways. You can use a stack or do pointer arithmetic. The interviewer came with a cheat sheet and would insist on pointer arithmetic only.

LinkedIn

Question d’entretien chez LinkedIn

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois