描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。

例如：给出的链表为 1->2->3->4->5->NULL，m=2，n=4

返回 1->4->3->2->5->NULL

思路1：两次遍历

1. 遍历找到要反转链表的前一个节点pre，即1
2. 子链表的头节点left=pre.next，即2
3. 遍历找到子链表的后一个节点5
4. 反转链表4->3->2->5，并返回新的头节点
5. 将pre连接上子链表

不足：当m和n相距过大时，反转子链表成本较大

public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode pre = node;
        //length为子链表长度
        int length = n - m;
        //找到反转链表的前一个节点
        while(m > 1) {
            m--;
            pre = pre.next;
        }
        //从子链表开始遍历，找到子链表的后一个节点
        ListNode left = pre.next;
        ListNode tail = left;
        while(length >= 0) {
            length--;
            tail = tail.next;
        }
        pre.next = reverse(left, tail);
        return node.next;
    }
    
    ListNode reverse(ListNode head, ListNode tail) {
        ListNode cur = tail;
        while(head != tail) {
            ListNode tmp = head.next;
            head.next = cur;
            cur = head;
            head = tmp;
        }
        return cur;
    }
}

思路2：一次遍历

1. 遍历找到要反转链表的前一个节点pre，即1
2. 子链表的头节点left=pre.next，即2
3. 反转长度为length的子链表：4->3->2
4. 将2指向子链表的后一个节点：4->3->2->5
5. 将pre接上子链表

和思路1不同的是，子链表的后一个节点需要遍历反转之后才能得到

public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode pre = node;
        int length = n - m;
        //找到子链表的前一个节点
        while(m > 1) {
            m--;
            pre = pre.next;
        }
        //反转长度为length的子链表，并返回反转链表的头节点
        ListNode left = pre.next;
        pre.next = reverse(left, length);
        return node.next;
    }
    ListNode reverse(ListNode head, int length) {
        //保存子链表的头节点
        ListNode left = head;
        ListNode cur = null;
        while(length >= 0) {
            ListNode tmp = head.next;
            head.next = cur;
            cur = head;
            head = tmp;
            length--;
        }
        //指向子链表的后一个节点
        left.next = head;
        return cur;
    }
}

思路3：使用栈

1. 遍历找到要反转链表的前一个节点pre，即1
2. 遍历将子链表节点全部入栈
3. 保存子链表的后一个节点
4. 将栈中元素出栈，接在原链表后面
5. 连接上子链表的后一个节点

public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode pre = node;
        Stack<ListNode> stack = new Stack<>();
        int length = n - m;
        while(m > 1) {
            m--;
            pre = pre.next;
        }
        head = pre.next;
        for(int i = 0; i <= length; i++) {
            stack.push(head);
            head = head.next;
        }
        while(!stack.isEmpty()) {
            pre.next = stack.pop();
            pre = pre.next;
        }
        pre.next = head;
        return node.next;
    }
}