92. 反转链表 II

1. 题目

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

示例 1：

img

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

示例 2：

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

提示：

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

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

2. 思路

  • 初始化result节点其next指针指向head作为头指针，最终结果将返回result.next节点（这么做的目的是为了防止头指针也需要反转的情况）

  • 初始化node节点值为result作为遍历时的元素，初始化index变量作为遍历时的下标

  • 初始化leftNode, rightNode, startLeftNode, endRightNode变量为null

  • 初始化preNode节点，当遍历链表时，实时更新该字段值

  • 依次遍历result链表，每次移动指针时index += 1，同时移动node以及记录preNode:

    • 当index == left时，意味着从该节点开始需要进行链表节点的反转，并更新leftNode节点值为当前节点，更新startLeftNode节点值为当前节点的上一个节点
    • 当index == right时，意味着到该节点为止，后续的链表节点无需反转，并更新rightNode节点值为当前节点，更新endRightNode节点值为当前节点的下一个节点
    • 当index的值位于left < index <= right时，实时反转链表，反转的思想是将当前节点的next指针指向上一个节点preNode

  • 完成遍历后，需要将原来的leftNode指向endRightNode，并且需要将startLeftNode的下一个节点指针next更新为rightNode

image-20230924173455871

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        var result = new ListNode();
        result.next = head;
        var node = result;
        var index = 0;
        
        ListNode leftNode = null;
        ListNode startLeftNode = null;
        ListNode rightNode = null;
        ListNode endRightNode = null;
        ListNode preNode = null;

        while (node != null) {
            if (index == left) {
                leftNode = node;
                startLeftNode = preNode;
            }

            if (index == right) {
                rightNode = node;
                endRightNode = rightNode.next;
            }

            var nextNode = node.next;

            if (index > left && index <= right) {
                node.next = preNode;
            }

            preNode = node;
            node = nextNode;
            index++;
        }

        if (leftNode != null) {
            leftNode.next = endRightNode;
        }

        if (startLeftNode != null) {
            startLeftNode.next = rightNode;
        }

        return result.next;
    }
}

4. 复杂度

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

image-20230924171337303