March.15.2022——206.反转链表

本文主要是介绍March.15.2022——206.反转链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

March.15.2022

206.反转链表

力扣题目链接

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：

输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

题解一：设置虚拟头节点

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode cur = head;ListNode prev = null;ListNode temp = null; //设置一个临时节点while(cur != null){  //在这里为什么不能写成 cur.next != null呢？temp = cur.next;  //为了防止链表断开 先保存要反转节点的下一个节点cur.next = prev;//将链表的指针反转prev = cur;//分别将 cur 和 prev 指针向前移动 cur = temp;}return prev;}
}

题解二：递归

递归需要遵守的重要规则

当程序正在执行一个方法的时候，就创建一个受保护的独立空间（栈空间）
方法的局部变量是独立的，不会相互影响，比如 n 变量
- 如果方法中使用的是引用类型的变量，那么就会共享该引用类型的数据
  
  （比如数组在堆中存放一份共享的数据不同的栈共享这一份数据）
递归必须向退出的递归条件逼近，否则就是无限递归，starkoverflowerror
当一个方法执行完毕的时候，或者遇到了return时就会返回，
遵守谁调用就将结果返回给谁，同时当方法制性完毕或者返回时，该方法也就执行完毕

class Solution {public ListNode reverseList(ListNode head) {return reverse(null,head);}private ListNode reverse(ListNode prev,ListNode cur){if(cur == null){return prev;}ListNode temp = null;temp = cur.next;//保存下一个节点 cur.next = prev;//反转//移动cur 和 prev的位置 更新！return reverse(cur,temp);}
}