92. 反转链表 II

一切尽力就好，活得开心就好。

参考92. 反转链表 II。

题目

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

反转[2,4]

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

解题思路

• 两次遍历：第一次遍历得到left和right两个节点以及前后节点,第二次遍历反转[left,right]区间。
• 一次遍历：遍历一次,先到达left的上一节点pre,然后开始从left反转到right,每次反转一次(pre和cur交换并且更新新的pre)。

两次遍历

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left == right) return head;
        //找左节点
        ListNode leftNode = head,leftPre = null;
        int index = 1;
        while(index < left){
            leftPre = leftNode;
            leftNode = leftNode.next;
            index++;
        }
        //找右节点
        ListNode rightNode = leftNode,rightNext = null;
        while(index < right){
            rightNode = rightNode.next;
            index++;
        }
        rightNext = rightNode.next;    
        //反转
        ListNode pre = leftPre;
        ListNode cur = leftNode;
        while(cur != rightNext) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //连接前后
        if(leftPre != null) leftPre.next = rightNode;
        leftNode.next = rightNext;
        //返回头结点
        return leftPre == null? rightNode : head;
    }
}

复杂度分析

• 时间复杂度：O(n)，一重循环进行两次,n为节点数量。
• 空间复杂度：O(1)，只使用常数个变量。

一次遍历

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0,head);//哨兵指向head处理left=1的情况
        //找左节点前一个节点
        ListNode leftPre = dummy;
        for(int i = 1; i < left; i++) leftPre = leftPre.next;
        //反转 核心:只修改一次next
        ListNode pre = leftPre;
        ListNode cur = leftPre.next;
        for(int i = left; i <= right; i++) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //反转后改为头为了pre 尾为leftPre.nex 下一个节点为cur
        leftPre.next.next = cur;//原先的头(leftPre.next)的next指向现在的尾
        leftPre.next = pre;//leftPre指向反转后的头
        return dummy.next;//返回头结点
    }
}

复杂度分析

• 时间复杂度：O(n),只进行一次遍历。
• 空间复杂度：O(1)。