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:

```java
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.