反转链表-技术圈

双指针迭代（原地）反转

current：表示迭代到的当前节点
prev：当前节点的上一个节点
Temp：主要用途是临时记录当前节点的下一节点，注意图中的虚线部分，在对current进行反转后，current失去了原下一节点next的指引，所以在反转之前需要通过temp临时节点记录下。

原链表数据：

step1：反转node1，将其next指向前一节点prev

step2：将node1赋值给prev，并且根据temp获取到原下一节点node2，将node2设为current，再按照step1中的操作对node2进行反转。

step3：和上面的step2操作一样，反转node3即双指针current与prev继续向下移动。

step4：反转node4

step5：反转node5

step6：当current为null时即代表反转完成

/**     * 双指针迭代反转，也叫原地反转     */    public static ListNode iteratorReverse(ListNode listNode){        //上一个节点        ListNode prev = null;        //当前节点        ListNode current = listNode;        while (current!=null){            /*备份与反转*/            //为了避免反转当前节点时丢失原下一节点引用，先备份下当前节点的下一节点。            ListNode temp = current.next;            //开始反转当前节点，将当前节点的next指向prev上一个节点            current.next = prev;            /*开始移动current和prev指针*/            //把当前节点赋值给上一节点，就相当于prev指针向前移动一位            prev = current;            //把备份的temp临时节点再赋值给当前节点，即相当于当前节点指针向前移动一位            current = temp;        }        return prev;    }

递归反转

列表天然的满足递归的3个使用条件：

大问题（大链表）可以拆成两个子问题（子链表）
子问题的求解方式和大问题相同
存在最小子问题（其实也就是终止条件）

step1：先将大链表按照head和剩余节点拆成两个子链表，也就是递归操作中的递。

step2：子链表求解

子链表反转规则，可以看成是两个节点之间进行反转，即

head.next.next = head
head.next = null

step3：将各节点按照子节点解决方式迭代，也就是归操作。最终结果为：

/**     * 递归反转     */    public static ListNode recursiveReverse(ListNode listNode) {        //终止递归的条件        if (listNode == null || listNode.next == null) {            return listNode;        }        ListNode node = recursiveReverse(listNode.next);        listNode.next.next = listNode;        listNode.next = null;        return node;    }