链表指定区间反转

方法一：

1.先将需要反转的区间进行分离后当成整个链表进行反转

2.再将反转后的区间与需要反转的区间的前后向后相邻的节点进行连接

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
 
/*思路：
1.将需要反转的区间进行分离出来，当做整个链表进行反转
2.将反转后的区间进行与反转区间的左右相邻的节点进行连接
*/
public class Solution {
     public ListNode reverseBetween (ListNode head, int m, int n) {
        //由于对于头结点和尾结点相对链表的其他节点是特殊的，因为是头结点是没有前驱的，尾指针
        //是没有后继的，但是由于对于链表中的操作中经常遇到递归做法，但是头尾节点却不符合规律
        //所以可以设置一个虚的头结点，和设置一个虚的尾结点
       ListNode dummy=new ListNode(-1);
       dummy.next=head;
       ListNode pre=dummy;
       ListNode cur,leftnode,rightnode;
       for(int i=1;i<=m-1;i++){
        pre=pre.next;
       }
       rightnode=pre;
       for(int i=1;i<=n-m+1;i++){
            rightnode=rightnode.next;
       }
       leftnode=pre.next;
       cur=rightnode.next;
       pre.next=null;
       rightnode.next=null;
       ReverseList(leftnode);
       pre.next=rightnode;
       leftnode.next=cur;
       return dummy.next;
    }
    public ListNode ReverseList(ListNode head){
        ListNode pre=null;
        ListNode cur=head;
        ListNode cur_next;
        while(cur!=null){
            cur_next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=cur_next;
        }
        return pre;
    }
}

方法二：

1.将需要反转的区间里的点依次插在反转区间的最前面

import java.util.*;
public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        //由于对于链表的头结点和尾结点相比于链表的中间的节点是不一样的，所以不能用递归处理，需要特殊处理
        //但是可以设置一个虚的头结点和尾结点，让这个虚的头结点指向表头，让尾结点指向虚的尾结点
      ListNode dummynode=new ListNode(-1);
      dummynode.next=head;
      ListNode pre,cur,cur_next;
      pre=dummynode;
      for(int i=1;i<=m-1;i++){
        pre=pre.next;
      }
      cur=pre.next;
      //每次都将需要反转的区间中的节点插到最前面
      for(int i=1;i<=n-m;i++){
        //先保留cur的下一个节点
        cur_next=cur.next;
        cur.next=cur_next.next;
        //注意这里是cur_next.next=pre.next而不是cur，多模拟几次就可以发现
        cur_next.next=pre.next;
        pre.next=cur_next;
      }
      return dummynode.next;
       
    }
}