## 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

You could make it much more clear by using previous, current and next as your auxiliary pointers and then iterate while current != null 🙂

LikeLiked by 1 person

Like this?

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;

}

It’s almost the same, but it’s a little more comprehensible.

LikeLike

Yeap, exactly! 🙂

LikeLike

thanks!

LikeLiked by 1 person