反转链表II

中间进行反转，两种方法：

力扣官方，就是要设置null，截断再和直接反转一样。 

class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {// 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论ListNode dummyNode = new ListNode(-1);dummyNode.next = head;ListNode pre = dummyNode;// 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点// 建议写在 for 循环里，语义清晰for (int i = 0; i < left - 1; i++) {pre = pre.next;}// 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点ListNode rightNode = pre;for (int i = 0; i < right - left + 1; i++) {rightNode = rightNode.next;}// 第 3 步：切断出一个子链表（截取链表）ListNode leftNode = pre.next;ListNode curr = rightNode.next;// 注意：切断链接pre.next = null;rightNode.next = null;// 第 4 步：同第 206 题，反转链表的子区间reverseLinkedList(leftNode);// 第 5 步：接回到原来的链表中pre.next = rightNode;leftNode.next = curr;return dummyNode.next;}private void reverseLinkedList(ListNode head) {// 也可以使用递归反转一个链表ListNode pre = null;ListNode cur = head;while (cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}}
}

方法二、我的方法。因为有数字，可以在循环里操作

public static ListNode reverseBetween(ListNode head,int left,int right) {if (head == null || left==right) return head;// 虚拟头节点--前指针 现指针 后指针ListNode dummy=new ListNode(0);dummy.next=head;ListNode pre=dummy;// 赋值、转向、移动  赋转移for(int i=0;i<left-1;i++){pre=pre.next;}ListNode cur=pre.next;ListNode nex=null;ListNode prev=null;// 就是这里for(int i=0;i<right-left+1;i++){nex=cur.next;cur.next=prev;prev=cur;cur=nex;}pre.next.next=cur;pre.next=prev;return dummy.next;}