92 reverse linked list2

https://leetcode.com/problems/reverse-linked-list-ii/

思路是记录start,end以及start左和end右，以及使用dummy head

不用dummy node主要的问题是反转之后要把segment左边界与新的segment左端相连，但是segment左边界是可能为null的，用了dummynode左边界一定不为null了

右边界是不是null其实并不太影响，我们并不会dereference右边界

/**
 * 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) {
        ListNode dummy = new ListNode(-1, head);
        ListNode leftNode = dummy;
        ListNode rightNode = dummy;
        
        // preLeft和nextRight是要翻转的segment的左右边界(不包含在segment里)
        // leftNode是反转之前segment的第一个元素，也是反转之后的最后一个
        while (left > 1) {
            leftNode = leftNode.next;
            left--;
        }
        ListNode preLeft = leftNode;
        leftNode = leftNode.next;
        
        while (right >= 1) {
            rightNode = rightNode.next;
            right--;
        }
        ListNode nextRight = rightNode.next;
        
        ListNode pre = preLeft;
        ListNode cur = leftNode;
        
        while (cur != nextRight) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        
        preLeft.next = pre;
        leftNode.next = nextRight;
        
        return dummy.next;
    }
}

不用dummy node的话是这样的

/**
 * 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) {
        int cnt = 1;
        ListNode pre = null;
        ListNode cur = head;
        
        while (cnt < left) {
            pre = cur;
            cur = cur.next;
            cnt++;
        }
        
        ListNode start = pre;
        ListNode startNext = cur;
        while (cnt <= right) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
            cnt++;
        }
        ListNode end = cur;
        if (start != null) {
            start.next = pre;
        } else {
            head = pre;
        }
        startNext.next = end;
        return head;
    }
}