[Solved] Reverse a singly linked list in Java

by


There are 2 problems:

  1. you are not saving the new head once it is returned (when you reach the end of the list), so the returned head is always going to be the one of the first stack of recursion, which is the original first node;
  2. you are not assigning node.next to null on the first node, so it will never become the new tail of the list.

This is the corrected code:

public Node reverse(Node head) {
    Node node = head;
    if (node.next == null) {
        head = node;
        return head;
    }
    Node next = node.next;

    // fix for problem 2, we transform the current node in the tail
    node.next = null;

    // fix for problem 1, head is now the tail node
    head = reverse(next);   

    next.next = node;

    return head;
}

solved Reverse a singly linked list in Java