Issues with reversing the linkedlist

114 views Asked by At

I'm trying to learn about linked list and it has been little challenging for me. I'm trying to reverse the link list with recursive method. Here is my code:

public class ListNode {
    Node head = null;

    int nodeCount= 0;

    int counter = 0;

    ListNode(){
        head = null;

    }

    public void insertNode( String name ) {

        if (head == null) {
            head = new Node(name, null);
            nodeCount++;
        } else {
            Node temp = new Node(name, null);
            temp.next = head;
            head = temp;


            nodeCount++;
        }
    }
        public Node reverseTest(Node L){

            // Node current = new Node(null,null);

            if(L == null || L.next ==null){
                return L;
            }

            Node remainingNode =  reverseTest(L.next);
            Node cur = remainingNode;
            while(cur.next !=null){
                cur=cur.next;
            }

            L.next = null;
            cur.next = L;

            return  remainingNode;

        }


    public static void main(String[] args){

        ListNode newList = new ListNode();
        newList.insertNode("First");
        newList.insertNode("Second");
        newList.insertNode("Third");
        newList.insertNode("Fourth");

        newList.reverseTest(newList.head);


    }
}

The problem I'm having with is the reverse method. When the method is over it only returns the last node with the value "First".Through the entire recursion remainingNode only holds and returs value from the base case which is confusing me. I was excepting it to move further through the nodes. After the method is executed newList holds only one node with next node as null and that node is the head now. I was assuming it will reverse the linkedlist with the sequence First --> Second--> Third --> Fourth. What am I doing wrong?

1

There are 1 answers

1
Joffrey On BEST ANSWER

Actually, everything works here. Your only problem is in your main method: you don't get the result of your method.

newList.reverseTest(newList.head);

You need to actually set the new head with the result:

newList.head = newList.reverseTest(newList.head);

This would have been easier to see if you had declared your method static:

newList.head = ListNode.reverseTest(newList.head);

As a bonus, here is a fully recursive equivalent:

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

    Node newHead = reverse(head.next);

    // head.next points to the new tail, we push the former head at the end
    head.next.next = head;
    // now head has become the new tail, we cut the end of the list
    head.next = null;

    return newHead;
}