Windows 7 Reverse a linked list in Java

[Rishab7]

Hi everyone,

I am trying to reverse a linked list in Java. I have been following the tutorial on how to reverse a linked list, but I am having trouble understanding the recursive approach. Can anyone help me understand how to reverse a linked list using recursion in Java?

Here is the code that I have so far:

public class ReverseLinkedList {

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

        Node reversedList = reverse(head.next);
        head.next.next = head;
        head.next = null;

        return reversedList;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);

        Node reversedList = reverse(head);

        System.out.println(reversedList.data); // 4
        System.out.println(reversedList.next.data); // 3
        System.out.println(reversedList.next.next.data); // 2
        System.out.println(reversedList.next.next.next.data); // 1
    }
}

I am not sure what and where I am doing wrong. Can somebody help me in debugging this code?

Thank you.

 

[ChatGPT]

Hi, The code you provided seems to be mostly correct for reversing a linked list using recursion. However, there is a small mistake in the code that is causing the issue. The issue lies in the line head.next.next = head;. This line should be head.next.next = head; in order to correctly reverse the next node in the list. Currently, this line is causing a NullPointerException because you have set head.next to null in the next line, which breaks the reference to the next node. To fix this issue, you need to store the reference to the next node in a temporary variable before assigning it to head.next.next. Here is the corrected code:

public class ReverseLinkedList {
    public static Node reverse(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node temp = head.next;
        Node reversedList = reverse(head.next);
        temp.next = head;
        head.next = null;
        return reversedList;
    }
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        Node reversedList = reverse(head);
        System.out.println(reversedList.data); // 4
        System.out.println(reversedList.next.data); // 3
        System.out.println(reversedList.next.next.data); // 2
        System.out.println(reversedList.next.next.next.data); // 1
    }
}

This should give you the correct reversed linked list as output. Hope this helps! Let me know if you have any further questions.