题目

• 给定一个链表，使其从m位置到n位置的链表进行反转，一次通过，链表的长度是在1<=m<=n<=链表长度
• 举例：给定链表1->2->3->4->5->NULL,m=2,n=4返回的应该是1->4->3->2->5->NULL

解题思路

• 只需要一次遍历该链表，同时对链表计数count,如果count值在m和n之间表示这一段节点都是需要反转
• 需要反转的部分我们可以采用头插法实现一边遍历一边反转
• 头插法需要考虑几个问题：我们需要找到m节点的前一个节点，如果m=1那么就是head就要开始反转，所以我在原始链表中增加一个front节点可以保证无论m是哪个值都可以实现链表节点反转
• 其次，m节点反转后是作为这一段反转节点的末尾，这时候是需要续接后面的节点，所以当遍历到count==m时，就采用一个遍历将这个链表变量reverseLast进行暂存，方便之后使用。
• 最后，关于reverseLast的next有两种情况，倘若n==链表长度，那么只需要指向NULL，但是如果n<链表长度，那么reverseLast的next需要指向后续的原始链表。
• 因为没有使用太多额外空间，空间复杂度为O(1)
• 也可以采用完全开辟一个新链表的方法，即是我对原始链表遍历，同时根据条件将原始链表的值创建到新链表中，但是这样会使用O(n)的空间。

解题源代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode front = new ListNode(0);
        front.next = head;
        ListNode pre = front, index = head;//index用于遍历，pre用于表示反转链表m的前一个链表节点
        ListNode reverseLast = null;//反转链表后的最后一个节点，也是反转前的第一个链表指针
        int count = 0;
        while (index != null) {
            count++;
            if (count == m) {
                reverseLast = index;//暂存
                ListNode temp = index;
                index = index.next;
                temp.next = null;
                pre.next = temp;
                continue;
            }
            if (count < m) {
                pre = index;//更新父节点
            }
            //采用头插法实现反转
            if (count > m && count <= n) {
                ListNode temp = index;
                index = index.next;
                temp.next = pre.next;
                pre.next = temp;
                continue;
            }
            if (count == n+1) {
                reverseLast.next = index;
                break;
            }
            index = index.next;
        }
        return front.next;
    }
}