Реверсивный связанный список в Java

Question

Я уже некоторое время работаю над проектом Java для класса. Это реализация связанного списка (здесь называемого AddressList, содержащего простые узлы с именем ListNode). Суть в том, что все должно быть сделано с помощью рекурсивных алгоритмов. Я был в состоянии сделать все отлично без одного метода: public AddressList reverse()

ListNode:

public class ListNode{
  public String data;
  public ListNode next;
}

Прямо сейчас моя reverse функция просто вызывает вспомогательную функцию, которая принимает аргумент для разрешения рекурсии.

public AddressList reverse(){
  return new AddressList(this.reverse(this.head));
}

С моей вспомогательной функцией, имеющей подпись private ListNode reverse(ListNode current).

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

Редактировать: Неважно, я понял это в то же время.

private AddressList reverse(ListNode current, AddressList reversedList){
  if(current == null) 
      return reversedList;
  reversedList.addToFront(current.getData());
  return this.reverse(current.getNext(), reversedList);
}

Пока я здесь, кто-нибудь видит проблемы с этим маршрутом?

Answer 1

В одном ответе есть код, который излагает его, но, возможно, вам будет проще начать снизу вверх, задавая и отвечая на крошечные вопросы (таков подход в «Маленьком Лиспере»):

1. Что является противоположностью нуля (пустой список)? нуль.
2. Что является обратным списку из одного элемента? элемент.
3. Что является обратным списку из n элементов? обратная сторона остальной части списка, за которой следует первый элемент.

---

public ListNode Reverse(ListNode list)
{
    if (list == null) return null; // first question

    if (list.next == null) return list; // second question

    // third question - in Lisp this is easy, but we don't have cons
    // so we grab the second element (which will be the last after we reverse it)

    ListNode secondElem = list.next;

    // bug fix - need to unlink list from the rest or you will get a cycle
    list.next = null;

    // then we reverse everything from the second element on
    ListNode reverseRest = Reverse(secondElem);

    // then we join the two lists
    secondElem.next = list;

    return reverseRest;
}

Answer 2

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

Это должно перевернуть односвязный список, вызываемый с помощью reverse (head, NULL); так что если бы это был ваш список:

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
    }
    

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

Answer 3

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

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;
}

Answer 4

Вот еще одно рекурсивное решение. У него меньше кода внутри рекурсивной функции, чем у некоторых, поэтому он может быть немного быстрее. Это C #, но я считаю, что Java будет очень похожа.

class Node<T>
{
    Node<T> next;
    public T data;
}

class LinkedList<T>
{
    Node<T> head = null;

    public void Reverse()
    {
        if (head != null)
            head = RecursiveReverse(null, head);
    }

    private Node<T> RecursiveReverse(Node<T> prev, Node<T> curr)
    {
        Node<T> next = curr.next;
        curr.next = prev;
        return (next == null) ? curr : RecursiveReverse(curr, next);
    }
}

Answer 5

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

• следи за головой
• Рекурс до конца списка ссылок
• Обратная связь

Состав:

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

Answer 6

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

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

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());

Answer 7

Мне кажется, это более чистое решение, напоминающее 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;
}

Answer 8

public Node reverseListRecursive(Node curr)
{
    if(curr == null){//Base case
        return head;
    }
    else{
        (reverseListRecursive(curr.next)).next = (curr);
    }
    return curr;
}

Answer 9

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

Answer 10

public void reverse() {
    head = reverseNodes(null, head);
}

private Node reverseNodes(Node prevNode, Node currentNode) {
    if (currentNode == null)
        return prevNode;
    Node nextNode = currentNode.next;
    currentNode.next = prevNode;
    return reverseNodes(currentNode, nextNode);
}