链表类总结

• 206. 反转链表

链表如何实现，如何遍历链表。链表可以保证头部尾部插入删除操作都是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;
    }
}