CONY的世界

92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

這題一開始用reverse list I 的想法來做，紀錄開始前一位為start 和開始第一位 end

因為這是要特別處理reverse list 相連接的地方，所以要特別處理 （至於連接方式沒什麼太特別，就是耐心解決所有連接case）

/**
 * Definition for singly-linked list.
 * public 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 prev = null, cur = head, start=null, end=null;
        for(int index=1; index<=n; index++){
            //System.out.println(cur);
            if(index == m-1)
                start = cur;
            else if(index == m)
                end = cur;

            if(index > m && index < n) {
                ListNode temp = cur.next;
                cur.next = prev;
                prev = cur;
                cur=temp;
            } else if(index == n){
                end.next = cur.next;
                if(start != null) start.next = cur;
                else head = cur;
                cur.next = prev;
                cur = end.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        return head;
    }
}

看討論別人的做法感覺更漂亮，所以也試做了一下，用到的想法是 start 是 reverse list 開始的第一位，
然後會不斷把then 往前放與prev 相接 （也就是說，prev.next 永遠會接reverse list 目前處理到最新要reverse的node，然後藉由往前把使它reverse)

              --------------------
              | --------             |
              | |        ｜           |
              v v        |            |
      prev     start then    .....     (reverse list end)

然後注意加了一個 dummy 開頭，主要是預防從頭開始reverse的情形（這種case時 start = dummy.next = head)，回傳時注意是從dummy.next 為頭

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(0), prev = dummy;
        dummy.next = head;
        for(int index=0;index<m-1;index++) prev = prev.next;
        
        ListNode start = prev.next, then = start.next;
        
        for(int index=0;index<n-m; index++){
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }
        return dummy.next; 
    }
}