链表类总结
链表如何实现，如何遍历链表。链表可以保证头部尾部插入删除操作都是O（1），查找任意元素位置O（N），快慢指针和链表反转几乎是所有链表类问题的基础，尤其是反转链表，代码很短，建议直接背熟。
206. 反转链表
注：本题对递归又有了新的认知，前面学习递归的思想，更多的是不要用人脑去计算递归过程，而是用一种通用的办法直接得出答案，这种通用的过程称之为递推公式，后续部分已经完成了，只要关注第k个和第k+1个的逻辑即可！
那么本题新的认知是，递归是由递和归组成，递的过程反映的思想就是拆解成子问题的思想，归的过程就是在处理递推公式（完成指定功能），所谓的递归出口就是最小子问题的结果！。
/**
* 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 prev = null;
ListNode cur = head;
while(cur != null){
// 若curr指针不空，记录下一个节点next
ListNode next = cur.next;
// cur指向前者
cur.next = prev;
// prev移动到cur
prev = cur;
// cur移动到下一个节点next
cur = next;
}
// 最后返回最后一个节点：prev
return prev;
}
}
/**
* 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) {
// 使用递归方式解决
// 最小子问题非递归出口
if( head == null ||head.next == null){
return head;
}
// 递归的递过程,这里的p实际上是最后的一个节点
ListNode p = reverseList(head.next);
// 递归的归过程：递归函数，也就是递推公式的处理
// head下一个指针指向head
head.next.next = head;
// head的下一个指针指向null
head.next = null;
// 最后返回最后一个节点p
return p;
}
}