Reverse Linked List II

    Example

    Given 1->2->3->4->5->NULL, m = 2 and n = 4, return
    1->4->3->2->5->NULL.

    Note

    Challenge

    Reverse it in-place and in one-pass

    题解

    1. 由于只翻转指定区域，分析受影响的区域为第m-1个和第n+1个节点
    2. 找到第m个节点，使用for循环n-m次，使用上题中的链表翻转方法
    3. 处理第m-1个和第n+1个节点
    4. 返回dummy->next
    2.  * Definition for ListNode
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode(int x) {
    7.  *         next = null;
    8.  *     }
    9.  * }
    10.  */
    11. public class Solution {
    12.     /**
    13.      * @param ListNode head is the head of the linked list 
    14.      * @oaram m and n
    16.      */
    17.     public ListNode reverseBetween(ListNode head, int m , int n) {
    18.         ListNode dummy = new ListNode(0);
    19.         dummy.next = head;
    21.         // find the mth node
    22.         ListNode premNode = dummy;
    23.         for (int i = 1; i < m; i++) {
    24.             premNode = premNode.next;
    25.         }
    27.         // reverse node between m and n
    28.         while (curr != null && (m <= n)) {
    30.             curr.next = prev;
    31.             prev = curr;
    32.             curr = nextNode;
    33.             m++;
    34.         }
    36.         // join head and tail before m and after n
    37.         premNode.next.next = curr;
    38.         premNode.next = prev;
    40.         return dummy.next;
    41.     }
    42. }
    1. 处理异常
    2. 使用dummy辅助节点
    3. 找到premNode——m节点之前的一个节点
    4. 以nNode和postnNode进行遍历翻转，注意考虑在遍历到n之前postnNode可能为空
    5. 连接premNode和nNode，premNode->next = nNode;
    6. 连接mNode和postnNode，

    务必注意node 和node->next的区别！！，node指代节点，而node->next指代节点的下一连接。