1、链表

一、第206题：反转链表

1、问题

image.png

2、解题思路

2.1、反转链表，一个向后的指针明显无法解决问题了，在不改变链表本身结构的情况下，可以手动记录遍历到的节点的preNode，curNode，nextNode。至于为什么需要三个指针，如下：
2.2、preNode：上一个节点指针。链表只有单向指针，无法直接获取上一个节点，所以需要在循环外面声明preNode，循环一次更新一次。
2.3、curNode：当前节点。
2.4、nextNode：反转时，curNode.next = preNode，如果再想使用curNode.next会发现已经被覆盖了，故需要记录。
2.4、反转之后，三个指针都同步向后挪动一位。

3、代码

class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
}
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode preNode = null;
        ListNode curNode = head;
        while(curNode != null) {
            // 临时存储next，避免丢失
            ListNode nextNode = curNode.next;
            // 反转
            curNode.next = preNode;

            // 向后移动
            preNode = curNode;
            curNode = nextNode;
        }
        return preNode;
    }
}

二、第92题：反转链表 II

1、题目

image.png

2、思路

2.1、把m到n位置的链表单独截取出来，反转之后，再拼接到原链表上。
2.2、mPre：截取要注意记录m位置上一个节点，便于后续把反转链表拼接回去。因为单链表都是向后指。
2.3、nNext：移动到n位置后，记录n的下一个位置，便于后续拼接。
2.4、mPre为null情况：如果从1开始翻转，mPre为null，mPre.next = preNode出空指针异常。此时，直接返回截取出来并反转的链表即可，不用拼接在mPre后面。

3、代码

class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
}
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(m == n) {
            return head;
        }
        ListNode preNode = null;
        ListNode curNode = head;
        ListNode nextNode = null;

        // 存储start
        ListNode start = curNode;
        // 将curNode挪动到m位置
        for(int i=0; i<m-1; i++) {
            preNode = curNode;
            curNode = curNode.next;
            nextNode = curNode.next;
        }
        // 记录m位置前一个节点，便于后续拼接
        ListNode mPre = preNode;
        // 记录m位置，后面翻转要从m开始
        ListNode mCur = curNode;

        // 将curNode从m 挪动到n位置
        for(int i=m; i<n; i++) {
            preNode = curNode;
            curNode = curNode.next;
            nextNode = curNode.next;
        }
        // 记录n位置的下一个节点，便于拼接
        ListNode nNext = nextNode;

        // 设置翻转后的节点下一个节点是 nNext
        preNode = nNext;
        // 从m位置开始翻转
        curNode = mCur;
        while(curNode != nNext) {
            // 存储next
            nextNode = curNode.next;
            // 反转
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }

        // mPre拼接翻转后的list，
        // 如果mPre为空，直接返回，否则返回刚开始记录的start
        if(mPre == null) {
            return preNode;
        }
        mPre.next = preNode;
        return start;
    }
}