本文转载自微信公众号《程序员熊》，作者程序员熊。转载本文请联系程序员小熊公众号。前言大家好，我是来自华为的“程序员熊”。相信大部分童鞋都知道，在处理“链表”相关问题时，常用的解题套路主要有“双指针”、“迭代”和“虚拟头节点”等。今天“小熊”主要介绍“递归”策略秒杀“链表”相关问题，让代码更“优雅”，并以两道常见面试题为例进行讲解，供大家参考，希望对您有所帮助。链表和递归链表具有自然的递归性。一个链表可以看出在头节点后面附加了一个更短的链表。这个更短的链表以原链表头节点的下一个节点为头节点，依次向内推，直到最后一个更短的链表为空，空本身也是一个链表（最基本的）.以单链表1->2->3->null为例，如下图所示：原链表看到原链表的头节点1，然后挂载一个更短的链表头节点+ashorterlinkedlisttocontinuetodismantuntilitcan'tdismantedSolvingShorterLinkedLists越来越短的链表有了这种思路，很多与“链表”相关的问题都可以用“递归”的思路来解决。剑指报价24.反向链表定义一个函数，输入链表的头节点，反转链表并输出反向链表的头节点。例子：输入：1->2->3->4->5->NULL输出：5->4->3->2->1->NULL限制：0<=节点数<=5000解题意是将链表反转，即原链表的头节点成为新链表的尾节点，原链表的尾节点成为新链表的头节点新的链表。如下图：反转前：原链表反转后：新链表的主要策略是：1.直接修改链表的值，如上图原链表所示如图，将原链表头节点值1改为原链表尾节点值，以此类推；2.让整个链表遍历，链表的尾节点指向它的前一个节点，以此类推。虽然这两种策略都有效，但在面试中要求“策略2”是很常见的。从上面的“递归和链表”我们可以看出，这个问题也可以用“递归的方法”来解决。如何通过“递归”解决？请参见下面的示例。《例子》链表1->2->3->null就是一个例子，如下图。例子不断遍历找到原链表作为尾节点，也就是新链表的头节点。原链表的尾节点再使尾节点指向它的前驱节点，以此类推。递归反转的详细步骤如下图所示：递归反转单链表代码展示「C」structListNode*reverseList(structListNode*head){/*递归终止条件*/if(head==NULL||head->next==NULL){returnhead;}??/*反转当前链表节点*/structListNode*newHead=reverseList(head->next);/*从原链表的尾节点到其前驱节点一byone*/head->next->next=head;/*防止循环*/head->next=NULL;/*返回新的链表头节点*/returnnewHead;}??「java」ListNodereverseList(ListNodehead){if(head==null||head.next==null){returnhead;}??ListNodenode=reverseList(head.next);head.next.next=head;head.next=null;returnnode;}当然这题可以也可以使用“迭代”方法完成。代码（python版）也很优雅，如下：ShowmetheCode"python"defreverseList(self,head:ListNode)->ListNode:cur,pre=head,Nonewhilecur:cur.next,pre,cur=pre,cur,cur.nextreturnpre《复杂度分析》时间复杂度：“O(n)”，n为链表长度。链表的每个节点都是颠倒的。空间复杂度：“O(n)”，其中n是链表的长度。递归调用的堆栈空间，最多n层。203、删除链表元素。给定一个链表头节点head和一个整数val。请删除链表中所有满足Node.val==val的节点，并返回一个新的头节点。示例1：输入：head=[1,2,6,3,4,5,6],val=6输出：[1,2,3,4,5]示例2：输入：head=[],val=1输出：[]例3：输入：head=[7,7,7,7],val=7输出：[]解题思路删除链表中给定值的节点，一般策略就是“找到给定值点值节点的前驱节点，然后使其指向给定值节点的后继节点”。例如，要删除链表1->2->3->null中节点值为3的节点，首先要找到它的前驱节点（值为2的节点），如图下图：删除一个给定值的结点从上面的“递归与链表”中的“递归与链表”可以看出，这道题也可以用“递归的方法”不断地求解删除较短链表中具有给定值的节点，然后将处理后的较短链表附加到其前驱节点。【注意】最后需要判断原链表的头节点是否为要移除的节点。【示例】以链表1->2->3->null为例，移除链表中给定值的节点的过程，如下图所示。实例动画展示代码「C++」ListNode*removeElements(ListNode*head,intval){/*递归终止条件*/if(head==NULL){returnNULL;}/*删除链表头节点后,值为val元素的节点*/head->next=removeElements(head->next,val);/*判断head节点是否为值为val的节点，然后返回*/returnhead->val==val?head->next:head;}??"Golang"funcremoveElements(head*ListNode,valint)*ListNode{ifhead==nil{returnhead}head.Next=removeElements(head.Next,val)ifhead.Val==val{returnhead.Next}returnhead}《复杂度分析》时间复杂度：“O(n)”，n为链表长度。递归需要遍历链表一次。空间复杂度：“O(n)”，其中n是链表的长度。递归调用栈最多不会超过n层。
