反轉連結串列2：
intel筆試題，給出指定區間，反轉連結串列，給出指定值，如果該區間存在該值，刪除它。
其實就是這題的變形，這題會了，這個筆試題也可以拿下了！
/** * 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） { //intel 筆試題，有緣人，如果看到了這裡，你應該多寫題，這樣考試時候才自信拿下 // 定義一個dummyHead， 方便處理 ListNode dummyHead = new ListNode（0）； dummyHead。next = head； ListNode leftNode = dummyHead； ListNode rightNode = dummyHead； while（left > 1）{//不是從0開始數，//這裡為什麼是1 ， 因為我從head 前面一位開始數的。我要先找到先驅節點 leftNode = leftNode。next； left——； } //left的前驅節點保留。leftPre ListNode leftPre = leftNode； //left的節點 leftNode = leftNode。next； while（right > 0）{ //這裡為什麼是0 ， 因為我從head 前面一位開始數的。 rightNode = rightNode。next； right——； } // 斷開後續連結串列；先儲存臨時的 ListNode temp = rightNode。next； rightNode。next = null； // 斷開聯絡 leftPre。next = null； // 斷開前驅聯絡 reverseNode（leftNode）； // 接上前續 leftPre。next = rightNode； // 接上後續 leftNode。next = temp； return dummyHead。next； //時間複雜度O（N）， 空間複雜度O（N） } private ListNode reverseNode（ListNode head）{ //反轉一個連結串列 if（head == null || head。next == null）{ return head； } ListNode cur = reverseNode（head。next）； head。next。next = head； head。next = null； return cur； }}
這種方法面試官會讓你最佳化空間。O（1）
class Solution { public ListNode reverseBetween（ListNode head， int left， int right） { // 定義一個dummyHead， 方便處理 ListNode dummyHead = new ListNode（0）； dummyHead。next = head； ListNode pre = dummyHead； // 找到前驅節點 for （int i = 0； i < left - 1； i++） { // 假如left == 2， i = 0 走1次， pre 指向第一個元素，剛剛好是left == 2 的前一個個 pre = pre。next； } // 找到左節點 ListNode leftNode = pre。next； ListNode next； // 頭插法， 把left 後面的元素插入pre 後面。 for （int i = 0； i < right - left； i++） { next = leftNode。next； // 臨時儲存一下，別丟棄了 leftNode。next = next。next；//跳過next ， 相當於刪除了後一個元素。 next。next = pre。next； // 把left 後面的元素插入pre 後面， 這個時候指向pre。next pre。next = next； // 把pre的後置指標改變位置， 指向next ，完成一次 頭插，，left後面的元素插入pre後面了。 } return dummyHead。next； }}
用手畫一個連結串列的指標，改變指標時候要先保留指標後面的值哦。
next = leftNode。next
； // 臨時儲存一下，別丟棄了
