[数据结构与算法]leetcode92-反转链表Ⅱ

一.题目描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

二.题目解析

public ListNode reverseBetween(ListNode head, int left, int right) {
        /*假设第一个元素head索引是1，翻转从left到right的链表，并返回头结点
        递归法：时间复杂度O(n),空间复杂度O(n)(递归解法需要堆栈)
        * */
        //起始索引为1时，问题就转化为了reverseN函数的场景
        if(left == 1){
            return reverseN(head,right);
        }
        //递归，直到转化成reverseN的问题
        ListNode newHead = reverseBetween(head.next,left - 1,right - 1);
        //索引1-left-1的节点无需翻转，只需更新其指向的节点为left-right段翻转后新的头结点即可
        head.next = newHead;
        //返回原头结点
        return head;
    }
    //要设置成全局变量，如果放在reverseN函数中每轮循环中的successor都不是同一个变量，预期应该始终是第n+1个节点
    ListNode successor = new ListNode();

    public  ListNode reverseN(ListNode head, int n){
        /*假设第一个元素head索引是1，翻转从1到N的链表，并返回新的头结点
        * */
        if(n == 1){
            //记录第n+1个节点（为了链表翻转之后与原链表的衔接）
             successor = head.next;
             return head;
        }
        //以head.next为起点，翻转索引为1-n-1的节点
        ListNode newHead = reverseN(head.next,n - 1);
        //实现“翻转”
        head.next.next = head;
        //此轮的原头结点，经历“翻转”后，其下个节点暂时指向successor
        head.next = successor;
        //newHead始终不变的
        return newHead;
    }

2.

public ListNode reverseBetween1(ListNode head, int m, int n) {
        /*类似头插法，将(m,n]之间的节点依次插在m的前面，最终形成了逆序
        时间复杂度O(n),空间复杂度O(1)
        * */
        //为了边界的单独判断，定义虚拟头结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        //pre指向m的前一个位置
        for(int i = 1; i < m; i++){
            pre = pre.next;
        }
        //head指向m节点
        head = pre.next;
        //将(m,n]之间的节点依次插在m的前面
        for(int i = m; i < n; i++){
            ListNode successor = head.next;
            head.next = successor.next;
            successor.next = pre.next;
            pre.next = successor;
        }
        return dummy.next;
    }

3.

public ListNode reverseBetween2(ListNode head, int m, int n) {
        /*分为三段去处理，时间复杂度O(n),空间复杂度O(1)
        * */
        //定义虚拟头结点方便统一处理
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode before = dummy;
        //最终before指向[m,n]段的上一个节点。
        for (int i = 1; i < m; i++) {
            before = before.next;
        }
        ListNode cur = before.next;
        ListNode nextCur = null;
        ListNode pre = null;
        //m-n段实现翻转
        for (int i = m; i <= n; i++) {
            //翻转前保存下下个要处理的节点
            nextCur = cur.next;
            //翻转
            cur.next = pre;
            //pre和cur指针顺序往后推移
            pre = cur;
            cur = nextCur;
        }
        //先把原m-n段的第一个节点（翻转段的最后一个节点）指向原m-n段后面段的第一个节点
        before.next.next = cur;
        //再把原m-n段前面的那个前驱节点指向m-n段翻转后的新的头结点
        before.next = pre;

        return dummy.next;
    }