LeetCode(力扣) 92题：反转链表 II----双指针迭代方法求解附带详细注释_leetcode 92

题目描述

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

示例

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

思路分析

这道题其实和上次讲的“反转链表”那道题目很相似，上次是对整个链表进行反转，这次是取区间，对区间内的链表部分进行反转。思路上呢就是首先将要反转的链表从原链表中取出，对其进行反转之后再拼接回原链表。思路比较简单，但是代码实现起来较繁琐，大家请看代码。

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:     
        # 定义反转链表函数，此函数在“反转链表”那一题已经讲过
        def reverse(node):
            before = node
            after = None
            while before:
                next = before.next
                before.next = after
                after = before
                before = next

            return after
        
        # 接下来就是要找到要反转的链表部分
        # 先定位反转链表部分的左节点
        # 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        dummy_node = ListNode(-1)
        dummy_node.next = head
        pre = dummy_node
        # 虚拟头节点向前移动 left - 1 步, 到达左节点的前一个结点
        for i in range(left - 1):
            pre = pre.next
        # pre节点继续向前移动right - left + 1步，到达右节点
        right_node = pre
        for j in range(right - left + 1):
            right_node = right_node.next
        # 定位到左节点
        left_node = pre.next
        # 保留右节点右边的部分，用于后边反转之后的拼接
        curr = right_node.next
        # 切出反转链表部分
        pre.next = None
        right_node.next = None
        # 反转链表
        reversed_linklist = reverse(left_node)
        # 将反转后的链表接入到原链表
        pre.next = reversed_linklist
        left_node.next = curr

        return dummy_node.next       
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

运行结果