How do you reverse a linked list?

Question

Daniel · Accepted Answer

Iterate through the linked list and push each node into a stack. Then pop through the entire stack and append each node to a new linked list. The new linked list will be the reverse of the original.

Utilisateur anonyme · Answer

How about doing it in place?

I think this works. Didn't test the full iteration, wrote in one go.
Get the first 3 nodes (if the list is less than 3, then just change the pointers). Iterate through list reversing the pointers of the first 2 tracked nodes, keep 3rd node as reference for the next iteration. I return the new root node:

public Node reverseLinkedList(Node n) {
    
    if (n == null) return null;
    
    if (n.next == null) {
        return n;
    }
    Node nN = n.next;
    
    if (nN.next == null) {
        n.next = null;
        nN.next = n;
        return nN;
    }
    Node nNN = nN.next;
    
    n.next = null;
    
    while (nNN.next != null) {
        nN.next = n;
        n = nN;
        nN = nNN;
        nNN = nNN.next;
    }
    
    nNN.next = nN;
    
    return nNN;
}

Meta

Question d’entretien chez Meta

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois