==========================努力奋斗财源广进==========================

一、算法题目

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。

二、题解

1、我的题解

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

import java.util.Stack;
public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        //设置虚拟头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
 
        ListNode pre = dummyNode;
        //1.走left-1步到left的前一个节点
        for(int i=0;i<m-1;i++){
            pre = pre.next;
        }
 
        //2.走right-left+1步到right节点
        ListNode rigthNode = pre;
        for(int i=0;i<n-m+1;i++){
            rigthNode = rigthNode.next;
        }
 
        //3.截取出一个子链表
        ListNode leftNode = pre.next;
        ListNode cur = rigthNode.next;
 
        //4.切断链接
        pre.next=null;
        rigthNode.next=null;
 
        //5.反转局部链表
        reverseLinkedList(leftNode);
 
        //6.接回原来的链表
        pre.next = rigthNode;
        leftNode.next = cur;
        return dummyNode.next;
    }
    //反转局部链表
    private void reverseLinkedList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            //Cur_next 指向cur节点的下一个节点
            ListNode Cur_next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = Cur_next ;
        }
    }
}

2、优秀题解

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
       // 
       //说明：方便理解，以下注释中将用left，right分别代替m,n节点 

    public ListNode reverseBetween (ListNode head, int m, int n) {
             //设置虚拟头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next =head;
        ListNode pre = dummyNode;
        for(int i=0;i<m-1;i++){
            pre = pre.next;
        }

        ListNode cur = pre.next;
        ListNode Cur_next ;
        for(int i=0;i<n-m;i++){
            Cur_next = cur.next;
            cur.next = Cur_next.next;
            Cur_next .next = pre.next;
            pre.next = Cur_next ;
        }
        return dummyNode.next;
    }
}

这道题的优秀解法看起来很复杂。但是理清之后就很简单。我们先看清三个变量的具体含义。 第一个变量pre:指的是待反转区域的前一个节点，为什么需要这个变量？我们在遍历反转区域的时候，将待反转的元素从链表当中删除之后，将其插入这个变量之后。 第二个变量：cur:指的的待反转的第一个元素，它其实是在随着遍历在变化的。 第三个变量Cur_next：这个其实很好理解，就是cur的下一个元素，也即是我们要摘掉链表上的元素，将其插入到pre节点之后的元素。

优秀题解相比于第一种更难理解，代码量很少，其复杂度和第一种算法差不多。后续复习的时候，可以多研究下，学习下。

三、解法心得

链表这块确实不够熟悉。还需要多加练习。今天周六，一定把链表给搞熟。 自己的解法其实是看答案的写，通过单步调试一点点慢慢理解。

四、自我监督

评论区记录复习记录