反轉(zhuǎn)鏈表 II
思路：遍歷鏈表，使在反轉(zhuǎn)范圍內(nèi)的節(jié)點(diǎn)依次插入到反轉(zhuǎn)范圍的最頭部，最終實(shí)現(xiàn)反轉(zhuǎn)。
方法：
- 創(chuàng)立空頭節(jié)點(diǎn)鸦概，鏈接head（當(dāng)head也在反轉(zhuǎn)范圍中時(shí)會(huì)用到）
- 維護(hù)以下節(jié)點(diǎn)：
2.1 節(jié)點(diǎn)a：left所在節(jié)點(diǎn)的前一節(jié)點(diǎn)
2.2 節(jié)點(diǎn)start：始終作為反轉(zhuǎn)范圍中的第一個(gè)節(jié)點(diǎn)
2.3 節(jié)點(diǎn)fir：初始反轉(zhuǎn)范圍的第一個(gè)節(jié)點(diǎn)，在遍歷過程中不斷指向向前插入的節(jié)點(diǎn)change的next節(jié)點(diǎn)
2.4 節(jié)點(diǎn)cur：遍歷游標(biāo)
2.5 節(jié)點(diǎn)change：需要交換的節(jié)點(diǎn) - 維護(hù)以下變量：
3.1 count：根據(jù)遍歷累加贰剥，用于比較left垢啼，right - 流程：
4.1 從空頭結(jié)點(diǎn)開始遍歷
4.2 當(dāng)遍歷到left前一節(jié)點(diǎn)，賦給a艘刚，并同時(shí)獲取left節(jié)點(diǎn)賦給start管宵，fir
4.3 遍歷到left+1節(jié)點(diǎn)，把cur賦給change，將change節(jié)點(diǎn)插入到a后
4.4 與此同時(shí)箩朴，始終保持fir節(jié)點(diǎn)的next節(jié)點(diǎn)是change的next節(jié)點(diǎn)岗喉。start節(jié)點(diǎn)始終是a節(jié)點(diǎn)的next節(jié)點(diǎn)，即反轉(zhuǎn)范圍的第一個(gè)節(jié)點(diǎn)炸庞。 - 當(dāng)遍歷完成進(jìn)行返回：
5.1 若反轉(zhuǎn)范圍包括原先的head節(jié)點(diǎn)钱床，則空頭節(jié)點(diǎn)派上用場(chǎng)，為反轉(zhuǎn)范圍的前一節(jié)點(diǎn)a埠居，返回a.next即為結(jié)果查牌。
5.2 若反轉(zhuǎn)范圍不包括head，則返回head即可滥壕。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if(head == null) return null;
ListNode a = null;
ListNode start = null;
ListNode fir = null;
ListNode nullhead = new ListNode();
nullhead.next = head;
ListNode cur = nullhead;
int count = -1;
while(cur != null || cur == nullhead){
count++;
if(count == left - 1){
a = cur;
start = a.next;
fir = start;
}
if(count > left && count < right + 1){
ListNode change = cur;
cur = cur.next;
a.next = change;
fir.next = change.next;
change.next = start;
start = a.next;
continue;
}
cur = cur.next;
}
if(left == 1) return a.next;
return head;
}
}
