LeetCode: Reverse Linked List II

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

这么一道小题做了一下午。。。真是太令我伤心了。

我的想法是 先找到开始反转的第一个元素的前面的那个元素，标记start。然后一边遍历 一边反转，最后前中后三段连在一起。

想法很简单，但是实现的很痛苦。。。

有一个特殊情况，如果要求反转的第一个元素是head，需要注意。因为在这种情况下，head是要改变的，其他时候head不需要改变。

所以可以在m==1的情况单独考虑，也可以给head之前加一个头结点，这样的话就不会有之前的问题。

我觉得第二种方法比较好。

n是最后一个元素的时候不存在特殊情况。。

public static ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode s = new ListNode(0);
        s.next = head;
        ListNode start = s;
        ListNode first = s;
        ListNode cur = s;
        ListNode next = s;
        ListNode nextnext = s;
        if (head == null) return head;
        
        for (int i=0; i<m-1; i++) {
            start = start.next;
        }
        
        first = start.next;
        cur = first;
        //cur cannot be null, because it is the first element to reverse
//        if (cur == null) return head;
        next = cur.next;
        
        for (int j=m; j<n; j++) {
            //next cannot be null, because if next is null 
            //then j == length>=n and jump out of loop;
            nextnext = next.next;
            next.next = cur;
            cur = next;
            next = nextnext;    
        }
        
        start.next = cur;
        first.next = next;
        
        return s.next;
    }