大厂面试算法系列-如何实现链表的逆序(二)-递归法

我会带着你远行 2022-12-30 14:58 63阅读 0赞

> **导语**  
>   接着上次的内容，上次博客中展示了原地进行单链表的逆序操作，当然除了原地逆序还可以通过递归的方式进行调用操作。下面就来看看通过递归的方式如何进行单链表的逆序操作。

### 递归法逆序链表 ###

假定原来的链表为1->2->3->5->4->7,递归的思路，首先就是将除了第一个节点以外的节点先进行逆序，然后将第一个节点添加到逆序的子链表后面。同理要逆序第二个节点，就需要将除了第一个节点以外的链表先进行逆序。通过这种方式就可以实现链表的完全逆序了。  
**第一次递归**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70_pic_center]  
**第二次递归**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70_pic_center 1]  
  如上图所示，通过两次的操作，可以简单的理解递归思想在这里的使用，也就是要实现签名的结果必须到最后一次操作完成之后才会进行最终结果的返回。这个有一点需要注意的就是递归的层级。建议不要太深。  
**代码实现如下**

public class Test{ 
    	private static LNode RecursiveReverse(LNode head){ 
    		//如果链表中只有一个元素或者链表为空
    		if(head==null||head.next==null){ 
    			return hread;
    		}else{ 
    			//先反转后面的节点
    			LNode newhead = RecursiveReverse(head.next);
    			// 把当前节点加到后续遍历节点的尾部
    			head.next.next = head;
    			head.next = null;
    			return newhead;
    		}
    	}
    	public static void Reverse(LNode head){ 
    		if(head == null){ 
    			return ;
    		}
    		//获取链表第一个结点
    		LNode firstNode = head.next;
    		//对链表进行逆序
    		LNode newhead = RecursiveReverse(firstNode);
    		//头结点指向逆序后链表的第一个结点
    		head.next = newhead;
    	}
    }

### 算法性能分析 ###

由于递归也只需要对链表进行一次递归遍历，所以算法的时间复杂度为O(n)。算法的思路比较清晰，也就是说从第一个节点开始，这里所说的第一个节点就是链表的最后一个结点，倒数第二个节点，倒数第三个节点，以此类推。当然这里需要有一个数据栈的操作，所以说需要注意的就是方法栈的深度。从这个操作方面来看，算法在数据量大的情况下，数据栈深度太大会影响性能。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/89007959008847e2ac41785bf0e3fa97.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25paHVpMTIz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/e6567c70858b4f5f9ac49c2bb4102a5a.png