输入一个链表,反转链表后,输出新链表的表头。
输入
{1,2,3,4,5}
返回值
{5,4,3,2,1}
初拿到这题,很容易联想到反转系列用java的api中提供了几个类似的api如Collections.reverse()
和StringBuilder.reverse()
。他们提供了直接对集合、字符串的反转api。需要的就是根据链表构建集合,再将集合反转,反转后再重新构建链表指向关系。代码如下:
public static ListNode reverseByList(ListNode head) {
//方法先判断入参
if (head == null) {
return null;
}
//只有一个元素的直接返回
if (head.next == null) {
return head;
}
List<ListNode> list=new ArrayList<>();
while(head!=null){
list.add(head);
head=head.next;
}
//直接使用Collections的reverse反转
Collections.reverse(list);
// 反转后重建指向关系
for(int i=0;i<list.size()-1;i++){
list.get(i).next=list.get(i+1);
}
//链表最后一元素的next置为空
list.get(list.size()-1).next=null;
return list.get(0);
}
上面的方法确实能解决问题,但是一般出到这题,考的不会是你的api的熟练程度,面试官一般会要求你自己实现反转过程。对于集合的反转,自己实现的通用算法是index为i的和index为size-1-i的元素位置进行对调进行实现。集合原理图如下:
集合反转代码实现如下:
public static void reverseList(List<ListNode> list){
// 如果只有0或者1个元素,不需要做处理
if(list.size()<=1){
return;
}
int size=list.size();
int half=(size-1)>>1;
//从中号位遍历到0号位,将i位与size-1-i位进行互换实现集合的反转
for(int i=half;i>=0;i--){
ListNode temp=list.get(size-1-i);
list.set(size-1-i,list.get(i));
list.set(i,temp);
}
}
对于链表反转,上面链表反转思路是转为集合,对集合进行互换位置反转,然后再重建指针指向。还有一种只针对链表反转更有效的方式,即直接改变指针指向即可。用一个pre保持指向之前的节点的指针,用一个current指针指向当前遍历节点。直接改变当前指针的指向,由指向下一个节点改造为指向前面的节点。原理图如下:
代码实现如下:
public static ListNode reverseLinkNode(ListNode head) {
//方法先判断入参
if (head == null) {
return null;
}
//只有一个元素的直接返回
if (head.next == null) {
return head;
}
// 用于保持之前的指针,便于current指向
ListNode pre = null;
ListNode current = head;
//temp用于保持当前节点的下一个节点的指针,使得遍历继续
ListNode temp;
while (current != null) {
temp = current.next;
current.next = pre;
pre = current;
current = temp;
}
//因为循环终止条件是到最后current为null了,链表的头节点应该是pre,即最后一个非空节点
return pre;
}
还有没有其他思路?在集合反转的时候除了交换对称位置的元素,如果想到 stack 的 FILO 特性,也很方面的使用 stack 进行反转集合,但是要额外使用一个n大小的栈空间。时间复杂度都是O(n)。java中需要用栈可以用LinkedList
实现。
对于链表反转主要两种思路:
一个是直接改变链表节点指针实现,即原先指向下一个节点的指针改为指向前一个节点,这种时间复杂度是O(n),空间复杂度是O(1),一次遍历完成,效率较高。
另一种即将链表转为集合,可以用Java的Collections.reverse()
直接反转或者用交换头尾元素的思路或者利用LinkedList
的 FILO特性用分别用addLast
与pollLast
方法进行添加和删除,反转集合后重建指针指向,这类思路,时间复杂度是O(n),空间复杂度是O(n)(因为创建新的列表需要空间,栈也同样需要),针对链表反转总体效率不如第一种。
-----------分割线-----------
说点题外话,我还在想个slogan,看别人结尾都带句话就觉得很吊的样子,看看别人。
我是小林,擅长图解的蓝银。 我是敖丙,你知道的越多,你不知道的越多。 我是小姐姐,一个不允许你走弯路的人。
我呢?陷入沉思。。。?
还有啊,要加我好友的速度了,我感觉要好友位快不够用了啊,想要进技术群的也可以加我哈,各路大佬、内推、提问应有尽有
。
- END -