Reverse Linked List II

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

For example:

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

Note:

题意大致是把一部分链表反转一下。这道题我竟然自己做出来了，撒花撒花~~~（但是不确定是否满足限制条件

解题思路：

我觉得这道题对我来说主要的问题在于在不断地变化next时，如何去保证不会丢失节点；还有就是in-place和in one-pass的限制。这道题画图做比较方便。先上代码（虽然效率还是不高）：

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public ListNode reverseBetween(ListNode head, int m, int n) {        int index = 1;        if(m == 1){            ListNode root = new ListNode(0);            root.next = head;            m = 2;            n++;            ListNode start = root;            ListNode end = root;            while(index
    
     
      
     
    

我把题目大致解析成下图的样子：

可以看到涉及的修改在（m-1）到（n+1）节点之间，所以我首先（17~23行，33~39行）找到（m-1）的位置处，并且把（m-1）和m分别记作start和end节点。

在下图中大致分解了一次循环（25~29行，41~45行）的内容：

start和end保持不变，并且把他们的next都向后移动一个节点，然而这样的挪动会导致有一个节点没有next可以用来访问他，所以我就把这个节点在最开始记录为temp，然后再反向过来。做n-m次即可，最开始的while中index是表示找到的（m-1），在后面的while只是为了作为限制条件（n-m+m-1），没有特殊意义。

最后就得到了结果，在m=1时，我新建了一个root节点虚拟（13~16行），最后返回root.next即可，过程与不从头开始相同。