Reverse Linked-List Recursive



I’ve traced through my code to reverse a linked-list using recursion, and I cannot find anything wrong with it, but I know it does not work. Can anyone please explain why?

Node reverseLL (Node head) {
  if(curr.next == null) {
    head = curr;
    return head;
  }

  Node curr = head.next;
  prev = head;
  head.next = prev;
  head = next;
  reverseLL(head.next);
}

Answer

Below is a working version of your code, added with some helping structures:

class LList {
    Node head;

    void reverse() {
        head = rev(head, head.next);
    }

    private Node rev(Node node, Node next) {
        if(next == null)    return node; //return the node as head, if it hasn't got a next pointer.
        if(node == this.head)   node.next = null; //set the pointer of current head to null.

        Node temp = next.next;
        next.next = node; //reverse the pointer of node and next.
        return rev(next, temp); //reverse pointer of next node and its next.
    }
}

class Node {
    int val;
    Node next;
    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
}


Source: stackoverflow