前言
一般工作中,可能不会自己去实现元素反转的操作。因为目前的高级语言基本已经帮我们实现好了,我们要做的就是使用好相关的函数就可以了。但是对于知识的认知不能只停留在表面,有些时候更需要去寻求底层的实现原理,这样一来,对于我们自身能力的提高有很大帮助!
数组元素的反转
有n个元素的数组,我们可以得到该数组的大小。需要做的就是把第一个元素和最后一个元素进行调换位置即可,对于奇数数组和偶数数组处理类似。只不过奇数数组我们不用管中间的那个元素,比如奇数数组处理思路如下:
int[] oddArray = new int[]{ 1, 2, 3 };
反转这个数组的方法只需要进行将索引为0的1和索引为2的3元素进行位置的调换即可完成。
偶数数组处理思路如下:
int[] oddArray = new int[]{ 1, 2, 3, 4 };
同奇数的处理思路一样,将数组索引为0的元素与索引为3的元素换位,将索引为1的元素与索引为2的元素进行换位。
明白了以上的解决思路,写代码就简单了,具体的实现方案如下:
1 |
|
单链表元素的反转
1.什么是链表?
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。——-摘抄自维基百科
2.定义链表数据结构
通过概念我们可以了解到,链表的结构应该包含当前节点的值,和指向下一个节点的指针元素。那么,便可以对其数据结构做如下定义:
1 | class ListNode { |
3.初始化链表
1 | public class LinkedListReverse { |
通过以上的方式我们创建了一个从1到9的单向链表。
4.反转单链表
反转思路:这个实现的思路和数组元素的反转类似,只不过需要做一点稍微的变化,我们知道单链表的最后一个元素指向null,有1-10之间的元素链表,只需要将值为1的节点引用指向null,值为2的节点引用指向1,以此类推,根据以上分析可以得到以下方法,暂且将方法命名为 reverse ,方法实现如下:
1 | public static ListNode reverse(ListNode head) { |
关于反转的详细思路结合reverse方法参考如下分析过程:
1 | /* |
Java实现数组元素的反转demo
https://gist.github.com/strongant/7e2baab6291a569586bab1b97b0b22c6
Java实现单链表的反转demo
https://gist.github.com/strongant/f31727433ce0af4d2f6afb14ff304a19