翻转一个链表
给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null
在原地一次翻转完成
翻转链表是一个很基础的题,同时也是面试中开场常问的题,那么他的难点在哪呢?
我们都知道单链表的数据结构如下:
public class ListNode {
private int val;
private ListNode next;
}
翻转的实现是怎样的呢?将当前节点的next指针指向前一个节点.对下一个节点进行同样的操作.
这里面有两个变量:
所以我们只需要在实现中维护前置节点及后继节点的值即可.
因此不多BB,上代码加注释!
首先是用递归方式实现:
/**
* 递归实现
*/
/**
* 递归实现,将前置节点作为参数传递,初始调用pre=null
*/
private static ListNode reverse2(ListNode head, ListNode pre) {
// write your code here
//如果当前节点为空,返回前置节点,这样可以再结束时拿到头结点
if (head == null) {
return pre;
}
//保存后继节点
ListNode next = head.next;
//将当前节点的next指针指向前置节点(翻转操作)
head.next = pre;
//翻转下一个节点及其前置节点
return reverse2(next, head);
}
然后是非递归实现:
/**
* 非递归实现,直接传入当前节点即可
*/
public static ListNode reverse(ListNode head) {
// write your code here
//初始化将前置及后继节点置为null
ListNode nextNode = null;
ListNode preNode = null;
//当前节点不为空
while (head != null) {
//记录后继节点
nextNode = head.next;
//翻转,将当前节点的next指针指向前置节点
head.next = preNode;
//记录当前节点(即下一次循环时的前置节点)
preNode = head;
//向后遍历
head = nextNode;
}
//为空时返回前置节点
return preNode;
}
运行结果如下(没有错误,我连续翻转了两次):
完。
2018-11-27 完成
以上皆为个人所思所得,如有错误欢迎评论区指正。
欢迎转载,烦请署名并保留原文链接。
联系邮箱:huyanshi2580@gmail.com