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是最后一个元素的时候不存在特殊情况。。
1 public static ListNode reverseBetween(ListNode head, int m, int n) { 2 ListNode s = new ListNode(0); 3 s.next = head; 4 ListNode start = s; 5 ListNode first = s; 6 ListNode cur = s; 7 ListNode next = s; 8 ListNode nextnext = s; 9 if (head == null) return head; 10 11 for (int i=0; i<m-1; i++) { 12 start = start.next; 13 } 14 15 first = start.next; 16 cur = first; 17 //cur cannot be null, because it is the first element to reverse 18 // if (cur == null) return head; 19 next = cur.next; 20 21 for (int j=m; j<n; j++) { 22 //next cannot be null, because if next is null 23 //then j == length>=n and jump out of loop; 24 nextnext = next.next; 25 next.next = cur; 26 cur = next; 27 next = nextnext; 28 } 29 30 start.next = cur; 31 first.next = next; 32 33 return s.next; 34 }
LeetCode: Reverse Linked List II
原文：http://www.cnblogs.com/longhorn/p/3536032.html