Why this linkedlist recursive method doesn't work?

Question

I tried to implement a recursive method to reverse a linked list, here is the code:

public class MyListNode {
int val;
MyListNode next;
MyListNode() {}
MyListNode(int val) { this.val = val; }
MyListNode(int val, MyListNode next) { this.val = val; this.next = next; }
public static void main(String[] args){
   MyListNode head = buildList(new int[]{1,2,3,4,5});
   MyListNode newHead = reverseList(head);
}

static MyListNode buildList(int[] a){
    MyListNode head = new MyListNode(a[0]);
    MyListNode current = head;
    for(int i=1; i<a.length; i++){
        current.next = new MyListNode(a[i]);
        current = current.next;
    }
    return head;
}

public static MyListNode reverseList(MyListNode head) {
    MyListNode newhead = null;
    recursiveReverse(head, newhead);
    return newhead;
}

static void  recursiveReverse(MyListNode head, MyListNode rest) {
    if(head == null){
        return;
    }
    MyListNode temp = head.next;
    head.next = rest;
    rest = head;
    head = temp;
    recursiveReverse(head, rest);
    System.out.println("rest->" + rest.val);
}

MyListNode iterativeReverse(MyListNode head){
    MyListNode prev = null;
    MyListNode curr = head;
    while(curr != null){
        MyListNode temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;
    }
    return prev;
}

}

I thought once the reference in heap memory changed in deeper recursive method it will remain the same after it return to caller. But it looks like something is wrong. Could you help to clarify?

In your recursiveReverse, the updated value of rest doesn't make it out of the method, to the caller. Try using the new value as a return value instead (updating the usage, of course) — Hans Keﬆing
– Hans Keﬆing, Commented Jun 27, 2020 at 14:06

user1532146 · Accepted Answer · 2020-06-27 15:38:15Z

1

static MyListNode  recursiveReverse(MyListNode head, MyListNode rest) {
    if(head == null){
        return null;
    }
    if(head.next == null){
        head.next = rest;
        return head;
    }
    MyListNode temp = head.next;
    head.next = rest;
    rest = head;
    head = temp;
    return recursiveReverse(head, rest);
}

after Hans Keﬆing's comment I got this working method.

answered Jun 27, 2020 at 15:38

user1532146

3134 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Mark Dibeh · Accepted Answer · 2020-06-27 15:50:30Z

0

Why dont you do something like that . I am sorry for syntax errors (i am posying via phone) .

Int[] arrayOne = {1,2,3,4,5,6,7};
List<int> headList = arrayOne.toList();
List<int> reverseList= headList.OrderByDesc(x=> IndexOf(x)).toList();

answered Jun 27, 2020 at 15:50

Mark Dibeh

4691 gold badge7 silver badges21 bronze badges

1 Comment

user1532146 Over a year ago

It's because the exam asks for a recursive implementation of reversing a linked list.

Collectives™ on Stack Overflow

Why this linkedlist recursive method doesn't work?

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related