学习到反向链接列表

-1

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。有什么我失踪了吗？

此外，如果您有如何解决这些类型的问题的提示，它真的会帮助我。我一直在编程一段时间。这对解决问题非常有用。我很容易想出天真的解决方案。但是，在数据结构和算法领域，我们通过不同的想法/方式想出一个解决方案，我总是认为它很短。

例如，在这个问题中，我从来没有想过使用递归有一个解决方案。我正在使用在其他地方查找的解决方案。如果我得到一些能够帮助我解决这些问题的技巧，这将会非常有帮助。

来源

2016-06-26 Raghavendra Gujar

了解如何使用调试器来执行分步代码。 –

这样写的方式让我想起了一个很棒的网站，我喜欢练习我的代码。 [HackerRank - 扭转链接列表]（https://www.hackerrank.com/challenges/reverse-a-linked-list）。既然你的标题说明你正在学习，我觉得这是一个扩展你的技能的好地方。:) –

问题在于你如何概念化你的链表头。当你构建你的列表，你分配：

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（如果它不为null）。

现在，来看看相反的方法：

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

这听起来是不是不可思议？我们有假的价值，我们故意忽略它，但现在我们已经覆盖它。我们用什么改写了它？

那么，如果reverse()工作正常，新的头将是旧的最后一个元素。在你的情况下，这将是... 4元素！但是我们忽略了toString()中的头部，所以4将永远不会被打印。

我运行你提供的代码，它实际上打印HEAD->3->2->1->0，这应该不会是一个惊喜，因为列表被颠倒过来了，而且现在ghost 0元素已经被推到了尽头。

我的建议是尽量保持结构简单：当列表为空时，头部应该为空。而不是while(temp.next != null)，也许你可以做while(temp != null)，因为我们不再有基节点（如果头是空的，head.next是非法的），并且temp.next最后一个元素的下一个应该总是为空（这不适用于add()，因为我们需要对最后一个元素的引用）。

来源

2016-06-26 03:22:33 zebasz

谢谢。你的解释是有道理的。我忽略了最后一个节点的值是反向列表中头部的值的事实。 –

你需要改变你的toString方法。

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

来源

2016-06-26 06:36:16

学习到反向链接列表

回答

相关问题