Reverse Linked List IIローカル反転チェーンテーブル@LeetCode

ローカル反転、ポイント:
1 dummyノードの利用
2キーを4つ記録:

反転区間前の最後の未反転ノードpreBegin

反転区間、反転後の第1ノードreHead

反転区間、反転後の最後のノードreverseEnd

反転区間後の最初の未反転ノードpostEnd

3 3ポインタ(reHead,precur,cur)でチェーンテーブルを反転

package Level4;

import Utility.ListNode;

/**
 * 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.
 *
 */
public class S92 {

	public static void main(String[] args) {
		int[] list = {1,2,3};
		ListNode head = ListNode.create(list);
		ListNode h = reverseBetween(head, 1, 2);
		h.print();
	}

	public static ListNode reverseBetween(ListNode head, int m, int n) {
		ListNode dummy = new ListNode(-1);			//   dummy             ！
		dummy.next = head;
		ListNode preBegin = dummy;			// preBegin           
		int cnt = 1;
		while(preBegin!=null && cnt<m){	//   preBegin   
			preBegin = preBegin.next;
			cnt++;
		}
		
		ListNode reverseEnd = preBegin.next;		//               ，              
		ListNode reHead = null;							//      
		ListNode cur = preBegin.next;
		cnt = 1;
		ListNode postEnd = null;						//                       
		while(cur != null && cnt<=n-m+1){
			ListNode preCur = cur;
			cur = cur.next;
			if(cnt == n-m+1){
				postEnd = preCur.next;
			}
			preCur.next = reHead;
			reHead = preCur;
			cnt++;
		}
		
		preBegin.next = reHead;
		if(reverseEnd != null){
			reverseEnd.next = postEnd;
		}
		
		return dummy.next;
	}

}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode beforeM = dummy;
        int cnt = 1;
        while(cnt < m) {
            beforeM = beforeM.next;
            cnt++;
        }
        
        ListNode begin = beforeM.next;
        ListNode end = begin;
        while(cnt < n) {
            end = end.next;
            cnt++;
        }
        
        ListNode afterN = end.next;
        
        // Reverse between m to n
        ListNode tmp = beforeM;
        ListNode cur = begin;
        while(cur != afterN) {
            ListNode next = cur.next;
            cur.next = tmp;
            tmp = cur;
            cur = next;
        }
        
        beforeM.next = end;
        if(begin != null) 
            begin.next = afterN;
        
        return dummy.next;                          
    }
}