Реверсивный связанный список в 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

public static ListNode recRev(ListNode curr){

    if(curr.next == null){
        return curr;
    }
    ListNode head = recRev(curr.next);
    curr.next.next = curr;
    curr.next = null;

    // propogate the head value
    return head;

}

Answer 2

Реверс по алгоритму.

public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head;    
    ListNode rHead = reverse(head.next);
    rHead.next = head;
    head = null;
    return rHead;
}

Итеративным

public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head;    
    ListNode prev = null;
    ListNode cur = head
    ListNode next = head.next;
    while (next != null) {
        cur.next = prev;
        prev = cur;
        cur = next;
        next = next.next;
    }
    return cur;
}

Answer 3

Это решение демонстрирует, что аргументы не требуются.

/**
 * Reverse the list
 * @return reference to the new list head
 */
public LinkNode reverse() {
    if (next == null) {
        return this; // Return the old tail of the list as the new head
    }
    LinkNode oldTail = next.reverse(); // Recurse to find the old tail
    next.next = this; // The old next node now points back to this node
    next = null; // Make sure old head has no next
    return oldTail; // Return the old tail all the way back to the top
}

Вот вспомогательный код, чтобы продемонстрировать, что это работает:

public class LinkNode {
    private char name;
    private LinkNode next;

    /**
     * Return a linked list of nodes, whose names are characters from the given string
     * @param str node names
     */
    public LinkNode(String str) {
        if ((str == null) || (str.length() == 0)) {
            throw new IllegalArgumentException("LinkNode constructor arg: " + str);
        }
        name = str.charAt(0);
        if (str.length() > 1) {
            next = new LinkNode(str.substring(1));
        }
    }

    public String toString() {
        return name + ((next == null) ? "" : next.toString());
    }

    public static void main(String[] args) {
        LinkNode head = new LinkNode("abc");
        System.out.println(head);
        System.out.println(head.reverse());
    }
}

Answer 4

Вот простой итеративный подход:

public static Node reverse(Node root) {
    if (root == null || root.next == null) {
        return root;
    }

    Node curr, prev, next;
    curr = root; prev = next = null;
    while (curr != null) {
        next = curr.next;
        curr.next = prev;

        prev = curr;
        curr = next;
    }
    return prev;
}

А вот рекурсивный подход:

public static Node reverseR(Node node) {
    if (node == null || node.next == null) {
        return node;
    }

    Node next = node.next;
    node.next = null;

    Node remaining = reverseR(next);
    next.next = node;
    return remaining;
}

Answer 5

Поскольку Java всегда передается по значению, для рекурсивного обращения связанного списка в Java обязательно возвращайте «новый заголовок» (головной узел после реверсии) в конце рекурсии.

static ListNode reverseR(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode first = head;
    ListNode rest = head.next;

    // reverse the rest of the list recursively
    head = reverseR(rest);

    // fix the first node after recursion
    first.next.next = first;
    first.next = null;

    return head;
}

Answer 6

PointZeroTwo получил элегантный ответ и то же самое в Java ...

public void reverseList(){
    if(head!=null){
        head = reverseListNodes(null , head);
    }
}

private Node reverseListNodes(Node parent , Node child ){
    Node next = child.next;
    child.next = parent;
    return (next==null)?child:reverseListNodes(child, next);
}

Answer 7

//Recursive solution
class SLL
{
   int data;
   SLL next;
}

SLL reverse(SLL head)
{
  //base case - 0 or 1 elements
  if(head == null || head.next == null) return head;

  SLL temp = reverse(head.next);
  head.next.next = head;
  head.next = null;
  return temp;
}

Answer 8

Так мы бы поступили в Opal - чистом функциональном языке программирования. И, ИМХО - делать это рекурсивно, имеет смысл только в этом контексте.

List Reverse(List l)
{
    if (IsEmpty(l) || Size(l) == 1) return l;
    return reverse(rest(l))::first(l);
}

rest (l) возвращает список, который является исходным списком без его первого узла. first (l) возвращает первый элемент. :: является оператором конкатенации.

Answer 9

//this function reverses the linked list
public Node reverseList(Node p) {
    if(head == null){
        return null;
    }
    //make the last node as head
    if(p.next == null){
        head.next = null;
        head = p;
        return p;
    }
    //traverse to the last node, then reverse the pointers by assigning the 2nd last node to last node and so on..
    return reverseList(p.next).next = p;
}

Answer 10

private Node ReverseList(Node current, Node previous)
    {
        if (current == null) return null;
        Node originalNext = current.next;
        current.next = previous;
        if (originalNext == null) return current;
        return ReverseList(originalNext, current);
    }