leetcode92.反转链表 II

92. 反转链表 II

中等（反转链表）

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

示例 1：

img

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

示例 2：

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

代码一：

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
# 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: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if not head or left == right:
            return head
        pre = root = ListNode(0)
        pre.next = head
        for _ in range(left-1):
            pre = pre.next
        l1 = pre
        l2 = pre.next
        temp = pre.next
        node = temp.next
        for _ in range(right-left):
            node1 = node.next
            node.next = temp
            temp = node
            node = node1
        l1.next = temp
        l2.next = node
        return root.next

代码二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        p0 = dummy = ListNode(next=head)  # 考虑left等于1的情况，添加哨兵节点
        for _ in range(left - 1):
            p0 = p0.next
        # 反转链表通用代码
        pre = None
        cur = p0.next
        for _ in range(right - left + 1):
            nxt = cur.next
            cur.next = pre  # 每次循环只修改一个 next，方便大家理解
            pre = cur
            cur = nxt

        # 详见视频
        p0.next.next = cur
        p0.next = pre
        return dummy.next

这类题型通用代码

1
2
3
4
5
6
7
pre = None
cur = head
while cur:
    nxt = cur.next
    cur.next = pre  # 每次循环只修改一个 next，方便大家理解
    pre = cur
    cur = nxt