反转链表
双指针迭代（原地）反转
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;}
评论