Quick problem: reverse a linked list

  • The iterative solution: 

Iterating through the list, we append the reversed result to the current node; then the reversed result encapsulates the current node; and finally, we advance in the list using a previously saved pointer.

public Node reverse(final Node node) {
    Node temp = node;
    Node reversed = null;
    while (temp != null) {
        Node next = temp.next;
        temp.next = reversed;
        reversed = temp;
        temp = next;
    }
    return reversed;
}
  • Another iterative solution (kudos Mihai, see comments):
public Node reverse(final Node node) {
    if (node == null) {
        return null;
    }

    Node previous = node;
    Node current = node.next;

    while (current != null) {
        Node next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }

    return previous;
}
  • The recursive solution:

The stopping conditions are either an empty list or the last node. Otherwise we deconstruct the problem by reverting the list represented by the successors of the current node; then the current node becomes the last node; finally, the immediate successor of the node (which is currently the last node of the reverted list) becomes the predecessor of the current node.

public Node reverse(final Node node) {
    if (node == null) {
        return null;
    }
    if (node.next == null) {
        return node;
    }
    Node next = node.next;
    Node reversed = reverse(node.next);
    next.next = node;
    node.next = null;
    return reversed;
}
Advertisements