[每日一题]翻转链表

数据结构和算法►链表 , , , , 评论

来源:

lintcode-翻转链表

描述

翻转一个链表

样例

给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null

挑战

在原地一次翻转完成

翻转链表是一个很基础的题,同时也是面试中开场常问的题,那么他的难点在哪呢?

解题思路

我们都知道单链表的数据结构如下:

1
2
3
4
5
6
7

public class ListNode {

 private int val;
 private ListNode next;

}

翻转的实现是怎样的呢?将当前节点的next指针指向前一个节点.对下一个节点进行同样的操作.

这里面有两个变量:

  1. 链表节点无法获知前置节点.
  2. 当你将next节点指向前置后,next指针被改变,无法继续向下遍历.

所以我们只需要在实现中维护前置节点及后继节点的值即可.

因此不多BB,上代码加注释!

首先是用递归方式实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 递归实现
 */
 /**
  * 递归实现,将前置节点作为参数传递,初始调用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);
 }

然后是非递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 非递归实现,直接传入当前节点即可
 */
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;
}

运行结果如下(没有错误,我连续翻转了两次):

完。




ChangeLog

2018-11-27 完成

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十

呼延十Developer

个人简介。