当我们在聊到链表反转的时候,一定说的都是单链表,双链表本身就具有前驱指针 Prev 和后续指针 next,无需进行翻转。
单链表反转,反转后的效果如下:
看起来很简单,只需要将单链表所有结点的 next 指向,指向它的前驱节点即可。引入一个栈结构,就可以实现。
在原本链表的数据结构之外,引入一个栈(数组也可),将单链表循环遍历,将所有结点入栈,最后再从栈中循环出栈,继续出栈的顺序,得到的就是反转后的单链表。
但是这样实现,有一个问题,它会额外消耗一个栈的内存空间,此时空间复杂度就变成了 O(n)。并且,栈会遇到的问题,使用此种方式都会遇到,例如栈的深度问题。
在排序算法中,有一个概念叫原地排序,指的是不需要引入额外的存储空间,在原数据结构的基础上进行排序。这种排序算法的空间复杂度是 O(1)。例如我们常见的冒泡排序、插入排序都是原地排序算法。
这里,我们也可以在原单链表的数据结构上,进行单链表反转。
原地单链表反转,是一种很基础的算法,但是有一些在面试中遇到这道题,思路不清晰时,一时半会也写不出来。
容易出错的点在于,指针丢失。在转换结点指针的时候,所需结点和指针反转顺序,都很重要,一不小心,就会丢掉原本的后续指针 next,导致链表断裂。
在上一篇文章中,带单链表时间复杂度为 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 里敲一遍,加深印象。
单链表翻转,还可以通过递归来实现,但是这里不推荐使用,大家了解一下就好了。
递归还是在借助函数调用栈的思想,其实本质上也是一个栈。没什么好说的,直接上代码。
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 中,自己手动敲一遍,加深印象。
本文对你有帮助吗?留言、点赞、转发是最大的支持,谢谢!