插图: 三种办法可以反转单个链接下文！

当我们谈论链表反转时，我们必须说它们都是单链表，而双链表本身具有前置指针Prev和下一个指针，而无需翻转.

单链表反转，反转后的效果如下:

这看起来非常简单，只需指向单链表的所有节点中的下一个节点，然后指向其前任节点即可. 可以通过引入堆栈结构来实现.

除了原始链表的数据结构外，还引入一个堆栈（也可以是数组），循环遍历单链表，将所有节点放入堆栈中，最后从堆栈中循环出堆栈，请记住堆栈的顺序，结果是一个反向的单链表.

但是此实现存在问题，它将消耗堆栈的额外存储空间，并且空间复杂度变为O（n）. 并且，堆栈遇到的问题将以这种方式遇到，例如堆栈深度更常见的问题.

接下来，我们看一下如何解决空间复杂性问题.

在排序算法中，有一个称为就地排序的概念，它是指在原始数据结构的基础上进行排序而不引入额外的存储空间. 该排序算法的空间复杂度为O（1）. 例如，我们常见的冒泡排序和插入排序是就地排序算法.

在这里，我们还可以在原始单链表的数据结构上反转单链表.

原位单链列表反转是一个非常基本的算法，但是其中一些在采访中遇到了这个问题. 如果这个主意不清楚，就不会写成一个半.

容易出错的地方是指针丢失. 转换节点指针时，所需的节点和指针反转顺序非常重要. 如果您不小心，则会丢弃下一个原始后续指针，从而导致列表损坏.

在上一篇文章中链表反转 java，单链接列表时间复杂度为O（1）的节点删除方法介绍了在删除单链接列表时，您需要知道之前和之后的三个节点. 翻转单链列表时也是如此.

当我们想要翻转一个节点的指针时，我们还需要知道三个节点.

这么多，只需转到代码.

static?class?Node?{
????int?data;
????Node?next;
????Node(int?data){
????????this.data?=?data;
????}
}
static?Node?reverseByLoop(Node?head)?{
????if?(head?==?null?||?head.next?==?null){
????????return?head;
????}
????Node?preNode?=?null;
????Node?nextNode?=?null;
????while?(head?!=?null){
????????nextNode?=?head.next;
????????head.next?=?preNode;
????????preNode?=?head;
????????head?=?nextNode;
????}
????return?preNode;
}

所有翻转链表的逻辑都在reverseByLoop（）方法中，其中头节点用作参数，反向后的返回值是反向后单链表的头节点.

最好自己在IDE中将其敲响，以加深您的印象.

单链表反转也可以通过递归来实现，但是不建议在这里使用，每个人都知道.

递归仍然使用函数调用栈的思想链表反转 java，实际上实际上是一个栈. 没什么可说的，直接进入代码即可.

static?Node?reverseByRecursion(Node?head){
????if(head?==?null?||?head.next?==?null){
????????return?head;
????}
????Node?newHead?=?reverseByRecursion(head.next);
????head.next.next?=?head;
????head.next?=?null;
????return?newHead;
}

这时，已经介绍了单链接列表反转的内容. 学习算法仍然需要考虑编写更多内容并进行练习. 建议您在IDE中手动将其敲门以加深印象.

本文来自本站，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-248104-1.html