转载

如何在Java中反转单链表？

在本文中，我将向您展示如何在没有递归的情况下在Java中反转单个链表。单链表，也称为链表，是一组节点，只能在一个方向上遍历，例如向前。链表中的每个节点都包含两个内容，一个数据和指向列表中下一个节点的指针。为了反转链表，我们需要遍历列表，在每一步我们都需要反转链接，例如在第一次迭代之后，head将指向null，而next元素将指向head。在到达链表尾部时遍历结束时，尾部将指向第二个最后一个元素，它将成为一个新头，因为您可以遍历此节点中的所有元素。

因为我们不能使用java.util.LinkedList来演示这个例子，因为它是一个双向链表。在双向链表中，您可以在两个方向上进行遍历，即向前和向后遍历，因为每个节点都包含对前一个节点和下一个节点的引用。请参阅Thomas H. Cormen的“算法简介”中的良好数据结构和算法手册，以了解有关链表数据结构的更多信息。

对于这个例子，我创建了我们自己的单链表类。与java.util.LinkedList类似，它还包含一个嵌套的静态类Node，它表示链接列表的节点。它包含一个整数属性来保存数据部分，另一个Node引用指向列表中的下一个。如果要创建通用链接列表，则应将int替换为泛型类型T，如此处所示。

为了证明我们的反向方法有效，我们不仅要创建链表，还要填充链表。为了填充，我们需要在单链表上实现add（）方法。你有两个选择，要么在头部或尾部添加元素，要添加元素是很容易的，因为它不需要遍历直到结束但是如果你想创建一个包含按顺序排列元素的列表添加然后我们需要在链表的末尾添加节点。

我还创建了一个print（）方法来打印单个链表的所有节点，用空格分隔。此方法非常有用，可以证明我们的反向方法是否正常工作，因为您可以在反转之前和之后打印链表。

无递归单链表的Java程序

这是我们的示例程序，演示如何在Java中反转链表。为了逆转，我首先创建了一个名为singlylinkedlist的类，它表示一个链表数据结构。我进一步实现了add（）和print（）方法，将元素添加到链接列表中，并按向前顺序打印。

反向链接列表的逻辑封装在reverse（）方法中。它从头部到尾部遍历链接列表，并在每个步骤中反转链接，例如，每个节点而不是指向开始指向上一个节点的下一个元素，这样，当到达最后一个元素时，整个链接列表将反转，然后该元素将成为链接列表的新头部。

<b>package</b> test;

<font><i>/**
 * Java Program to reverse a singly list without using recursion.
 */</i></font><font>
<b>public</b> <b>class</b> LinkedListProblem {

  <b>public</b> <b>static</b> <b>void</b> main(String[] args) {

    </font><font><i>// creating a singly linked list</i></font><font>
    SinglyLinkedList.Node head = <b>new</b> SinglyLinkedList.Node(1);
    SinglyLinkedList linkedlist = <b>new</b> SinglyLinkedList(head);

    </font><font><i>// adding node into singly linked list</i></font><font>
    linkedlist.add(<b>new</b> SinglyLinkedList.Node(2));
    linkedlist.add(<b>new</b> SinglyLinkedList.Node(3));
    </font><font><i>// printing a singly linked list</i></font><font>
    linkedlist.print();

    </font><font><i>// reversing the singly linked list</i></font><font>
    linkedlist.reverse();

    </font><font><i>// printing the singly linked list again</i></font><font>
    linkedlist.print();

  }

}
</font><font><i>/**
 * A class to represent singly list in Java
 * 
 * @author WINDOWS 8
 *
 */</i></font><font>
<b>class</b> SinglyLinkedList {

  <b>static</b> <b>class</b> Node {

    <b>private</b> <b>int</b> data;
    <b>private</b> Node next;

    <b>public</b> Node(<b>int</b> data) {
      <b>this</b>.data = data;
    }

    <b>public</b> <b>int</b> data() {
      <b>return</b> data;
    }

    <b>public</b> Node next() {
      <b>return</b> next;
    }
  }

  <b>private</b> Node head;

  <b>public</b> SinglyLinkedList(Node head) {
    <b>this</b>.head = head;
  }

  </font><font><i>/**
   * Java method to add an element to linked list
   * @param node
   */</i></font><font>
  <b>public</b> <b>void</b> add(Node node) {
    Node current = head;
    <b>while</b> (current != <b>null</b>) {
      <b>if</b> (current.next == <b>null</b>) {
        current.next = node;
        <b>break</b>;
      }
      current = current.next;
    }
  }

  </font><font><i>/**
   * Java method to print a singly linked list
   */</i></font><font>
  <b>public</b> <b>void</b> print() {
    Node node = head;
    <b>while</b> (node != <b>null</b>) {
      System.out.print(node.data() + </font><font>" "</font><font>);
      node = node.next();
    }
    System.out.println(</font><font>""</font><font>);
  }

  </font><font><i>/**
   * Java method to reverse a linked list without recursion
   */</i></font><font>
  <b>public</b> <b>void</b> reverse() {
    Node pointer = head;
    Node previous = <b>null</b>, current = <b>null</b>;

    <b>while</b> (pointer != <b>null</b>) {
      current = pointer;
      pointer = pointer.next;

      </font><font><i>// reverse the link</i></font><font>
      current.next = previous;
      previous = current;
      head = current;
    }

  }
}
Output
1 2 3 
3 2 1 
</font>

您可以看到链接列表已反转，前面的1是第一个元素，现在是最后一个元素，而3是链接列表或头的第一个元素。

所有这些都是关于如何在Java中不使用递归来反转单链表。这个解决方案中没有使用递归，而是使用迭代。您可以看到reverse（）方法中的while循环。

原文 https://www.jdon.com/51601

正文到此结束

所属分类： Java 编程技术

本文标签： windows Windows 8 java http list 遍历递归数据 LinkedList id https IO node ORM
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二