Learning Обратный Связанный список

Question

У меня есть следующий код, чтобы полностью изменить Связанный список:

public class ProgrammingInterviews { 

    public static void main(String[] args) { 
     List list = new List(); 
     list.add(new Node(1)); 
     list.add(new Node(2)); 
     list.add(new Node(3)); 
     list.add(new Node(4)); 
     list.reverse(); 
     System.out.println(list); 
    } 

} 

class List { 
    Node head; 
    public List() { 
     head = new Node(0); 
    } 

    public void add(Node node) { 
     if (head.next == null) { 
      head.next = node; 
     } else { 
      Node temp = head.next; 
      while (temp.next != null) { 
       temp = temp.next; 
      } 
      temp.next = node; 
     } 
    } 

    public void reverse() { 
     this.head = reverse(this.head); 
    } 

    private Node reverse(Node n) { 
     if (n == null || n.next == null) { 
      return n; 
     } 
     Node remaining = reverse(n.next); 
     n.next.next = n; 
     n.next = null; 
     return remaining; 

    } 

    public String toString() { 
     Node temp = head; 
     String result = "HEAD"; 
     while (temp.next != null) { 
      result = result + "->" + temp.next.data; 
      temp = temp.next; 
     } 
     return result; 
    } 
} 

class Node { 
    int data; 
    Node next; 

    public Node(int data) { 
     this.data = data; 
    } 
} 

Я пытаюсь заставить его печатать HEAD->4->3->2->1 с безрезультатно. Но, это печать HEAD->3->2->1. Я чего-то не хватает.

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

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

Answer 1

Проблема заключается в том, как вы концептуализируете голову связанного списка. Когда вы создаете свой список, вы назначаете:

public List() { 
    head = new Node(0); 
} 

Список теоретически пуст, но у нас уже есть элемент! Ваша структура данных на самом деле не представляет данные точно, хотя в большинстве случаев вы игнорируете это, взглянув на head.next. Например:

public String toString() { 
    Node temp = head; 
    String result = "HEAD"; 
    while (temp.next != null) { 
     result = result + "->" + temp.next.data; 
     temp = temp.next; 
    } 
    return result; 
} 

Вы идете по списку, глядя на temp.next. Поскольку мы начинаем во главе, мы никогда не смотрим на его значение, и первое значение, которое мы печатаем, - head.next (если оно не является нулевым).

Теперь посмотрим на обратном методе:

public void reverse() { 
    this.head = reverse(this.head); 
} 

ли это звучит странно? У нас была поддельная ценность, и мы сознательно игнорировали ее, но теперь мы ее перезаписали. И что мы перезаписали?

Хорошо, если reverse() работает нормально, новая голова будет старым последним элементом. В вашем случае это будет ... элемент 4! Но мы игнорируем голову в toString(), поэтому 4 никогда не будут напечатаны.

Я запустил код, который вы предоставили, и он на самом деле печатает HEAD->3->2->1->0, что не должно удивлять, поскольку список был отменен, и этот элемент-призрак 0 теперь был нажат до конца.

Мой совет здесь заключается в том, чтобы сохранить структуру простой: когда список пуст, голова, вероятно, должна быть нулевой. И вместо while(temp.next != null), может быть, вы можете сделать while(temp != null), так как у нас больше нет базового узла (если голова равна нулю, head.next является незаконным), а temp.next на последнем следующем элементе всегда должно быть нулевым (это не относится к add(), так как нам нужна эта ссылка на последний элемент).

Answer 2

Вам нужно изменить свой метод toString.

public String toString() { 
    Node temp = head; 
    String result = "HEAD"; 
    while (temp != null) { 
     result = result + "->" + temp.data; 
     temp = temp.next; 
    } 
    return result; 
}