一乌企、第206題：反轉(zhuǎn)鏈表

1虑润、問題

image.png

2、解題思路

2.1加酵、反轉(zhuǎn)鏈表拳喻，一個(gè)向后的指針明顯無法解決問題了，在不改變鏈表本身結(jié)構(gòu)的情況下猪腕，可以手動(dòng)記錄遍歷到的節(jié)點(diǎn)的preNode冗澈，curNode，nextNode陋葡。至于為什么需要三個(gè)指針亚亲，如下：
2.2、preNode：上一個(gè)節(jié)點(diǎn)指針腐缤。鏈表只有單向指針捌归，無法直接獲取上一個(gè)節(jié)點(diǎn)，所以需要在循環(huán)外面聲明preNode岭粤，循環(huán)一次更新一次惜索。
2.3、curNode：當(dāng)前節(jié)點(diǎn)剃浇。
2.4巾兆、nextNode：反轉(zhuǎn)時(shí)猎物，curNode.next = preNode，如果再想使用curNode.next會(huì)發(fā)現(xiàn)已經(jīng)被覆蓋了臼寄，故需要記錄霸奕。
2.4、反轉(zhuǎn)之后吉拳，三個(gè)指針都同步向后挪動(dòng)一位。

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) {
            // 臨時(shí)存儲(chǔ)next留攒，避免丟失
            ListNode nextNode = curNode.next;
            // 反轉(zhuǎn)
            curNode.next = preNode;

            // 向后移動(dòng)
            preNode = curNode;
            curNode = nextNode;
        }
        return preNode;
    }
}

二、第92題：反轉(zhuǎn)鏈表 II

1嫉嘀、題目

image.png

2炼邀、思路

2.1、把m到n位置的鏈表單獨(dú)截取出來剪侮，反轉(zhuǎn)之后拭宁，再拼接到原鏈表上。
2.2瓣俯、mPre：截取要注意記錄m位置上一個(gè)節(jié)點(diǎn)杰标，便于后續(xù)把反轉(zhuǎn)鏈表拼接回去。因?yàn)閱捂湵矶际窍蚝笾浮?br> 2.3彩匕、nNext：移動(dòng)到n位置后腔剂，記錄n的下一個(gè)位置，便于后續(xù)拼接驼仪。
2.4掸犬、mPre為null情況：如果從1開始翻轉(zhuǎn)，mPre為null绪爸，mPre.next = preNode出空指針異常湾碎。此時(shí)，直接返回截取出來并反轉(zhuǎn)的鏈表即可奠货，不用拼接在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;

        // 存儲(chǔ)start
        ListNode start = curNode;
        // 將curNode挪動(dòng)到m位置
        for(int i=0; i<m-1; i++) {
            preNode = curNode;
            curNode = curNode.next;
            nextNode = curNode.next;
        }
        // 記錄m位置前一個(gè)節(jié)點(diǎn)仇味，便于后續(xù)拼接
        ListNode mPre = preNode;
        // 記錄m位置呻顽，后面翻轉(zhuǎn)要從m開始
        ListNode mCur = curNode;

        // 將curNode從m 挪動(dòng)到n位置
        for(int i=m; i<n; i++) {
            preNode = curNode;
            curNode = curNode.next;
            nextNode = curNode.next;
        }
        // 記錄n位置的下一個(gè)節(jié)點(diǎn)，便于拼接
        ListNode nNext = nextNode;

        // 設(shè)置翻轉(zhuǎn)后的節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)是 nNext
        preNode = nNext;
        // 從m位置開始翻轉(zhuǎn)
        curNode = mCur;
        while(curNode != nNext) {
            // 存儲(chǔ)next
            nextNode = curNode.next;
            // 反轉(zhuǎn)
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }

        // mPre拼接翻轉(zhuǎn)后的list丹墨，
        // 如果mPre為空廊遍，直接返回，否則返回剛開始記錄的start
        if(mPre == null) {
            return preNode;
        }
        mPre.next = preNode;
        return start;
    }
}