Инвертирование связанного списка в Java, рекурсивно

Алгоритм должен будет работать над следующей моделью,

• отслеживают голову
• , Рекурсивно вызывают до конца связи Реверса linklist

Структура:

Head    
|    
1-->2-->3-->4-->N-->null

null-->1-->2-->3-->4-->N<--null

null-->1-->2-->3-->4<--N<--null

null-->1-->2-->3<--4<--N<--null

null-->1-->2<--3<--4<--N<--null

null-->1<--2<--3<--4<--N<--null

null<--1<--2<--3<--4<--N
                       |
                       Head

Код:

public ListNode reverse(ListNode toBeNextNode, ListNode currentNode)
{               
        ListNode currentHead = currentNode; // keep track of the head

        if ((currentNode==null ||currentNode.next==null )&& toBeNextNode ==null)return currentHead; // ignore for size 0 & 1

        if (currentNode.next!=null)currentHead = reverse(currentNode, currentNode.next); // travarse till end recursively

        currentNode.next = toBeNextNode; // reverse link

        return currentHead;
}

Вывод:

head-->12345

head-->54321

Меня задали этот вопрос на интервью и раздражали, что я возился с ним, так как я был немного возбужден.

Это должно инвертировать отдельно связанный список, названный с реверсом (голова, ПУСТОЙ УКАЗАТЕЛЬ); таким образом, если это было Вашим списком:

1->2->3->4->5->null
it would become:
5->4->3->2->1->null

    //Takes as parameters a node in a linked list, and p, the previous node in that list
    //returns the head of the new list
    Node reverse(Node n,Node p){   
        if(n==null) return null;
        if(n.next==null){ //if this is the end of the list, then this is the new head
            n.next=p;
            return n;
        }
        Node r=reverse(n.next,n);  //call reverse for the next node, 
                                      //using yourself as the previous node
        n.next=p;                     //Set your next node to be the previous node 
        return r;                     //Return the head of the new list
    }
    

редактирование: я сделал как 6 редактирований на этом, показав, что это все еще немного коварно для меня lol

Я прошел половину пути (до нуля и одного узла, как указано в плинтусе), но потерял след после выполнения рекурсивного вызова. Однако после прочтения поста у постамента я пришел к следующему:

Node reverse(Node head) {
  // if head is null or only one node, it's reverse of itself.
  if ( (head==null) || (head.next == null) ) return head;

  // reverse the sub-list leaving the head node.
  Node reverse = reverse(head.next);

  // head.next still points to the last element of reversed sub-list.
  // so move the head to end.
  head.next.next = head;

  // point last node to nil, (get rid of cycles)
  head.next = null;
  return reverse;
}

void reverse(node1,node2){
if(node1.next!=null)
      reverse(node1.next,node1);
   node1.next=node2;
}
call this method as reverse(start,null);

Я думаю, что это более чистое решение, напоминающее LISP

// Example:
// reverse0(1->2->3, null) => 
//      reverse0(2->3, 1) => 
//          reverse0(3, 2->1) => reverse0(null, 3->2->1)
// once the first argument is null, return the second arg
// which is nothing but the reveresed list.

Link reverse0(Link f, Link n) {
    if (f != null) {
        Link t = new Link(f.data1, f.data2); 
        t.nextLink = n;                      
        f = f.nextLink;             // assuming first had n elements before, 
                                    // now it has (n-1) elements
        reverse0(f, t);
    }
    return n;
}

Я знаю, что это старое сообщение, но большинство ответов не являются хвостовыми рекурсивными, т.е. они выполняют некоторые операции после возврата из рекурсивного вызова, и поэтому не являются самыми эффективными.

Вот хвостовая рекурсивная версия:

public Node reverse(Node previous, Node current) {
    if(previous == null)
        return null;
    if(previous.equals(head))
        previous.setNext(null);
    if(current == null) {    // end of list
        head = previous;
        return head;
    } else {
                    Node temp = current.getNext();
        current.setNext(previous);
        reverse(current, temp);
    }
    return null;    //should never reach here.
} 

Вызов с:

Node newHead = reverse(head, head.getNext());