CODEWITHSUNDEEP
javarecursionlinked-list
Mutating Algorithm
Mutating Algorithm

Reputation: 2758

Reversing a linked list recursively in a class method

I have the following instance variables inside my SinglyLinkedList class.

/* head is a reference to the front of the list (first element)
 * by default, head is initialized to null */
private Node head;

/* tail is a reference to the back of the list (last element)
 * by default, tail is initialized to null */
private Node tail; 

/* length is an integer that represents the size of our list,
 * by default it is assigned a value of 0 */
protected int length;

What I would like to do is write a method called recursiveReverse() that reverses a SinglyLinkedList object recursively. Such as list.recursiveReverse()

I have some ideas which don't seem to be working without passing in a Node object 

public SinglyLinkedList recursiveReverse() {
    static Node temp = head;
    if(temp == null) return null;
    if(length == 1) return this;

    Node temp_2 = temp.next;
    temp.next = null;
    // here is where i am stuck with the recursive call
    // is passing a Node as an argument the only way ?
    // if so, then how do I pass it in a class method ?
    // make the method static ?
 }

Upvotes: 0

Views: 1440

Answers (1)

Wasi Ahmad
Wasi Ahmad

Reputation: 37691

This should work for you.

public ListNode reverseList(ListNode head) {
    if(head==null || head.next == null)
        return head;

    //get second node    
    ListNode second = head.next;
    //set first's next to be null
    head.next = null;

    ListNode rest = reverseList(second);
    second.next = head;

    return rest;
}

Reference: Reverse a Singly Linked List.

Upvotes: 1

Related Questions