数据结构和算法基础篇（四）从链表谈递归

前面我们谈了一些递归算法，包括尾递归算法。期间我们还穿插了一种动态规划的实现思路用于实现斐波那契数列。上一讲，我们甚至实现了文件夹的递归，这样当我们需要检索一个文件的时候，可以用递归去实现了。

今天，我们继续谈一谈递归，同时将涉及到不同类型的数据结构。本篇以Leetcode中第466题：链表长度计算为例，讲解递归算法的应用。

466. 链表节点计数

描述

计算链表中有多少个节点.

样例

给出 , 返回 .

分析：

在链表结构中，我们知道判断节点为空，说明该节点为空。

如果node的下一个节点为空，说明自己是最后一个节点。

链表的节点定义如下：

/** * Definition for ListNode * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */

下面我们用循环的思路先来看看怎么解决的。

方法1：循环

publicclassSolution{/** *@paramhead: the first node of linked list. *@return: An integer */publicintcountNodes(ListNode head){

if(head ==null)return;intcount=;

while(head!=null) { count++; head = head.next; }

returncount; }}

思路2：递归

publicclassSolution{publicintcountNodes(ListNode head){if(head ==null)return;

return (1+countNodes(head.next));}

小结：

一般大部分递归算法都可以转化为非递归算法。但是递归的效率会比循环慢，

而且递归的层次太深，容易导致栈溢出。

我们接下来再看几个链表方面使用递归算法的题目。

255. 查找一个链表节点

题意：在链表中查找一个节点，如果找到就返回，找不到就返回null。

这里我们不介绍非递归算法了，相信你们都能写出来。下面我们看看递归怎么实现。

代码如下：

35. 翻转一个链表

样例

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

先给出非递归算法如下：

publicclassSolution{publicListNodereverse(ListNode head){if(head==null||head.next==null)returnhead; ListNode pre=null; ListNode p=head; ListNode next;

while(p!=null) { next=p.next; p.next=pre; pre=p; p=next; }

returnpre; }}

递归版实现：

publicclassSolution{publicListNodereverse(ListNode head){if(head ==null|| head.next ==null)returnhead; ListNode newHead = reverse(head.next);//一直循环到链尾head.next.next = head;head.next =null;returnnewHead;}}

总结：

我们今天一共讲解了三道Leetcode题目，分别使用递归解决了链表长度计算、查找某一个节点（判断某一个节点也可以使用）、反转链表。

思考：

我们留下1道题目，供后续练习。

LeetCode第378题将二叉查找树转换成双链表。这个题目可以使用递归解决。