面试热题（反转链表）

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

       链表的题，大部分都可以用指针或者递归可以做，指针如果做不出来的话，建议多声明几个指针就可以做的出来了

方法一：

       因为链表中的头结点也有可能进行反转操作，所以我们为了不失一般性，创建一个虚拟头结点进行操作

       我们需要旋转[left,right]区间内的链表结点，所以我们就必须要知道left的上一个结点是谁，所以我们可以使用快慢指针进行操作，slow慢指针指向我们left的上一个结点,对区间内的节点进行反转，过程如下：

 源代码如下：

 public ListNode reverseBetween(ListNode head, int left, int right) {//如果头结点为空或者是头结点的后继点为空的话直接返回headif(head==null||head.next==null){return head;}//创建一个虚拟头结点ListNode dummyHead=new ListNode(0);dummyHead.next=head;//设置两个指针ListNode slow=dummyHead;//慢指针-->指向left指针指向节点的上一个节点ListNode fast=dummyHead.next;//快指针  将left指针与right指针中的节点加到left指针前面(包括right指针)//进行移动,将slow指针移向left指针的前一个节点for (int i = 1; i <left; i++) {slow=slow.next;fast=fast.next;}//将left和right指针中的节点移向left节点前(包括right指针对应的节点)for (int i = 0; i <right-left; i++) {ListNode removeNode=fast.next;fast.next=fast.next.next;removeNode.next=slow.next;slow.next=removeNode;}//返回头结点后的链表长度return dummyHead.next;}

方法二：

在以前学习得到过程中我们已经学过了链表翻转（必会）

//这几行代码必须得会，链表题最多的就是翻转，你可以直接当一个api去用
public ListNode reverse(ListNode root){if(root==null||root.next==null){return root;}//前扑ListNode pre=null;ListNode cur=root;//后继ListNode next=null;while(cur!=null){next=cur.next;cur.next=pre;pre=cur;cur=next;}//返回的是翻转后的头结点return pre;}

       现在我们只需要找到需要翻转链表区间的前扑后继，然后通过前扑的next指向翻转后的头结点，让反转后的尾结点指向后继，这道题就解出来了

 

源代码如下(这种方法比较推荐，比较容易理解)：

 public ListNode reverseBetween(ListNode head, int left, int right) {if(head==null||left>=right){return head;}//找到left的前驱节点，因为会设计头结点的操作，所以要创建一个虚拟头结点ListNode dummyNode=new ListNode(0,head);ListNode pre=dummyNode;//找到对应的前驱节点for (int i =1; i <left; i++) {pre=pre.next;}//未反转链表的头结点ListNode leftNode=pre.next;ListNode rightNode=leftNode;pre.next=null;//找到未反转链表的尾结点for (int i = 1; i <=right-left; i++) {rightNode=rightNode.next;}//找到后继ListNode end=rightNode.next;rightNode.next=null;ListNode newStartNode=reverse(leftNode);pre.next=newStartNode;leftNode.next=end;return dummyNode.next;}//反转链表public ListNode reverse(ListNode root){if(root==null||root.next==null){return root;}ListNode pre=null;ListNode cur=root;ListNode next=null;while(cur!=null){next=cur.next;cur.next=pre;pre=cur;cur=next;}return pre;}