链表之反转链表专题
如题，LeetCode 206
看到反转链表，我们要思考的核心点在于如何让链表的结点指针指向的方向反转
对于反转链表，一般有迭代或者递归两种思考方向
第一种：迭代
在这种方案中，做题总结出了双指针迭代比较高效，同时有一种双指针的迭代公式
具体的动画效果可以参考LeetCode官方题解
while(cur!=null) { //记录当前节点的下一个节点 tmp = cur.next; //然后将当前节点指向pre cur.next = pre; //pre和cur节点都前进一位 pre = cur; cur = tmp; }
比如，在这个题当中，
step1：使用临时节点 tmp 记录当前节点的下一个结点（和我们常用的借用第三个数交换另外两个数的值思想一致）
step2：控制下一个结点的方向反转
step3：移动当前节点和前驱节点
起始状态为下图所示，那么，我们肯定要记录当前节点的下一个结点，我们使用一个临时的指针用于存储达到交换的目的，这里的思想和常用的交换两个数借用第三个数的思想一致。
class Solution { public ListNode reverseList(ListNode head) { //申请节点，pre和 cur，pre指向null ListNode pre = null; ListNode cur = head; ListNode tmp = null; while(cur!=null) { //记录当前节点的下一个节点 tmp = cur.next; //然后将当前节点指向pre cur.next = pre; //pre和cur节点都前进一位 pre = cur; cur = tmp; } return pre; } }
第二种：递归
首先，我们看到这种题肯定会下意识的思考：
step1: 将头结点先移动到最后
step2: 将节点指针的顺序反过来（在这里还要注意防止循环链表的出现，所以要让head.next = null）
step3: 递归调用，返回当前的结点
class Solution { public ListNode reverseList(ListNode head) { //递归终止条件是当前为空，或者下一个节点为空 if(head==null || head.next==null) { return head; } //step1：递归调用，将头结点移动到最后，这里的cur就是最后一个节点 ListNode cur = reverseList(head.next); //step2：控制结点指针方向反转 //所以head.next.next 此时的head为4的结点，head.next为5的结点，head.next.next指向head就是5->4 head.next.next = head; //此时的head还是为4，如果设置这个的话，那么head.next指向的是5，此时结点4和结点5之间时双向链表，为了防止链表循环，需要将head.next设置为空 head.next = null; //每层递归函数都返回cur，也就是最后一个节点 return cur; } }
这个题就更加能让我们弄懂了
迭代的解法
class ListNode{ int val; ListNode listNode; public ListNode(int x){ val = x; } } public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { //初始化一个节点值为0的空节点 ListNode dummy = new ListNode(0); //让该结点指向头结点 dummy.next = head; //构建一个prev结点为当前空节点 ListNode prev = dummy; //迭代调用，记录当前prev节点的移动 while (m > 1) { prev = prev.next; m--; n--; } //结束上述while循环的条件是prev结点已经指向了要交换的结点的起始结点 head = prev.next; // 这里假设第m个结点到第n个结点以5->3->4为例 while (n > 1) { //next -> 3 ListNode next = head.next; //将头结点下一个结点指向紧挨着头结点的下一个结点的下一个结点 比如 5->3->4 ，此时5->4 head.next = head.next.next; // 3 -> 5 next.next = prev.next; // 此时将第m-1个结点指向 3，这个时候相当于 head -> 3 -> 5 ->4，相当于交换了第m个和第m+1个结点的位置，再迭代，直到n为0 prev.next = next; n--; } return dummy.next; } }
