92.反转链表 II

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

示例 1：

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

示例 2：

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

提示：

• 链表中节点数目为 n
• $1\le n\le 500$
• $-500\le Node.val\le 500$
• $1\le left\le right\le n$

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

解法一(模拟)

思路分析

1. 结合206.反转链表进行求解;
2. 可以将链表进行分段链接, 记录需要反转链表节点左边的前一个节点leftPre和右边节点的后一个节点tailRight;
3. 再将链表反转后进行链接; 即leftPre.next指向反转链表后的新节点, 反转链表后的末尾节点指向tailRight;

实现代码

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
		// 创建虚拟头节点   避免特殊情况需要特殊处理
		ListNode dummy = new ListNode(-1);
		dummy.next = head;
		ListNode leftPre = dummy;   // 获取反转链表左节点的前一个节点
		for (int i = 0; i < left-1; ++ i) {
			leftPre = leftPre.next;
		}
		// 记录反转链表的左起始节点 - 反转链表后的尾节点
		ListNode leftHead = leftPre.next;
		// 记录反转链表的右终止节点 - 反转链表后的首节点
		ListNode rightTail = leftPre;
		for (int i = 0; i < right-left+1; ++ i) {
			rightTail = rightTail.next;
		}
		// 记录反转链表后 链表尾节点应该继续链表的节点
		ListNode tailRight = rightTail.next;
		// 截断需要反转的链表段进行反转
		leftPre.next = null;
		rightTail.next = null;
		// 执行反转
		ListNode pre = null;
		ListNode cur = leftHead;
		while (cur != null) {
			ListNode t = cur.next;
			cur.next = pre;
			pre = cur;
			cur = t;
		}
		// 反转后进行链接
		leftHead.next = tailRight;
		leftPre.next = rightTail;
		return dummy.next;
    }
}

运行结果

2024/10/09 21:37:01

解答成功:

执行耗时:0 ms,击败了100.00% 的Java用户

内存消耗:40.2 MB,击败了78.25% 的Java用户

复杂度分析

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$

解法二(一次扫描)

思路分析

1. 解法一的反转过程中, 获取反转链表的左右起始节点需要进行一次遍历, 反转也需要进行一次遍历; 思考是否可以只需一次遍历即可完成反转;
2. 通过反转链表的规律可以发现, 每次反转结束后, pre指向新反转链表的头部, 而cur则是指向新反转链表的尾部;
3. 在该题中, 链表反转后, cur指向未反转链表前的右端的下一个节点tailRight; 即只需令反转链表的尾部指向tailRight, 未反转链表左端的前一个节点leftNode指向新反转链表头部pre; 即可完成反转;

实现代码

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 创建虚拟头节点   避免特殊情况需要特殊处理
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode leftPre = dummy;   // 获取反转链表左节点的前一个节点
        for (int i = 0; i < left-1; ++ i) {
            leftPre = leftPre.next;
        }
        // 反转链表
        // 每次反转链表结束后: pre指向新链表头节点, cur指向反转链表的下一个节点
        ListNode pre = null;
        ListNode cur = leftPre.next;
        for (int i = 0; i < right-left+1; ++ i) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        leftPre.next.next = cur;
        leftPre.next = pre;
        return dummy.next;
    }
}

运行结果

2024/10/09 22:08:13

解答成功:

执行耗时:0 ms,击败了100.00% 的Java用户

内存消耗:40.4 MB,击败了21.29% 的Java用户

复杂度分析

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$