[Leetcode][第206题][JAVA][反转一个单链表][递归][迭代]

短命女 2023-03-02 10:46 68阅读 0赞

#### 【问题描述】\[简单\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 递归 自底向上 ######

*  基本条件/终止条件：当前节点或者下一个节点==null
 *  递推关系： head.next.next = head

在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]

**时间复杂度：O(N) 空间复杂度：O(N)**  
![在这里插入图片描述][20200729005033631.png]

class Solution { 
    	public ListNode reverseList(ListNode head) { 
    		//递归终止条件是当前为空，或者下一个节点为空
    		if(head==null || head.next==null) { 
    			return head;
    		}
    		//这里的cur就是最后一个节点
    		ListNode cur = reverseList(head.next);
    		//这里请配合动画演示理解
    		//如果链表是 1->2->3->4->5，那么此时的cur就是5
    		//而head是4，head的下一个是5，下下一个是空
    		//所以head.next.next 就是5->4
    		head.next.next = head;
    		//防止链表循环，需要将head.next设置为空
    		head.next = null;
    		//每层递归函数都返回cur，也就是最后一个节点
    		return cur;
    	}
    }

###### 2. 递归 自顶向下 ######

*  寻找递推关系
 *  创建新函数，将「自底向上-范式」中的最终结果计算依赖的中间变量提取为函数的参数 -> prev为中间变量
 *  寻找递归基本情况，跳出时返回基本情况的结果与中间变量的计算结果（最终结果） -> 遍历完毕后，返回头节点pre
 *  根据函数参数与中间变量重新计算出新的中间变量 -> ListNode next = node.next;
 *  修改参数 -> node.next = prev;（调转方向 第一个指向了null）
 *  递归调用并返回（该处的返回由基本情况条件触发）-> reverse(node, next);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 6]

**时间复杂度：O(N) 空间复杂度：O(N)**

public ListNode reverseList(ListNode head) { 
            return reverse(null, head);
        }
    
        public ListNode reverse(ListNode prev, ListNode node) { 
            if (node == null) { 
                return prev;
            }
            // logic
            ListNode next = node.next; // node=1 next=2
            node.next = prev; // 1->null、2->1
            return reverse(node, next); // 1 2
        }

class Solution { 
        ListNode pre = null, tmp = null;
        public ListNode reverseList(ListNode head) { 
            if (head == null)
                return pre;
            tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
            return reverseList(head);
        }
    }

###### 3. 双指针 循环结构 ######

*  第一个指针叫 pre，最初是指向 null 的。
 *  第二个指针 cur 指向 head，然后不断遍历 cur。
 *  每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
 *  迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 7]

**时间复杂度：O(N) 空间复杂度：O(1)**  
![在这里插入图片描述][20200729005018653.png]

class Solution { 
    	public ListNode reverseList(ListNode head) { 
    		//申请节点，pre和 cur，pre指向null
    		ListNode pre = null;
    		ListNode cur = head;
    		ListNode tmp = null;
    		while(cur!=null) { 
    			//记录当前节点的下一个节点
    			tmp = cur.next;
    			//然后将当前节点指向pre
    			cur.next = pre;
    			//pre和cur节点都前进一位
    			pre = cur;
    			cur = tmp;
    		}
    		return pre;
    	}
    }

#### 【总结】 ####

###### 1. 「自顶向下、自底向上、循环结构」三种方法完成 ######

###### 2.递归 ######

在实现递归函数之前，有两件重要的事情需要弄清楚:

递推关系：一个问题的结果与其子问题的结果之间的关系。  
基本情况：不需要进一步的递归调用就可以直接计算答案的情况。可理解为递归跳出条件。  
一旦我们计算出以上两个元素，再想要实现一个递归函数，就只需要根据递推关系调用函数本身，直到其抵达基本情况。

###### 3.递归模板套路 ######

由下到上  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 8]

参考链接：https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/  
递归学习链接：https://blog.csdn.net/dadongwudi/article/details/107649161

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230208/bae935530ba54c83a5434db123230bc3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230208/e7f34d2f05dc4388aab05b08755bbb3a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: /images/20230208/d721ad18915646d6b8c6c147f16803c4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: /images/20230208/23452dde3ee84f8f9d73a44c8716c8d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: /images/20230208/c0757b24696940a9a54a65d094a5bc13.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 5]: /images/20230208/b61b154432bd4cadbedbf697b65defa2.png
[20200729005033631.png]: /images/20230208/c979fcc5288b48e6a058e08ba0532b9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 6]: /images/20230208/6232ec59f7ae493d9bd4fc100c0e9230.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 7]: /images/20230208/4b4a734b03fb46358d5dd8043b452dc9.png
[20200729005018653.png]: /images/20230208/7159bc752b9d45b99bed0891347a6ba0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 8]: /images/20230208/00ef406b24954a9b93b023d048933d2d.png