92. 反转链表 II

Difficulty
Medium
Tags
链表
URL
https://leetcode-cn.com/problems/reverse-linked-list-ii/
Star
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
notion imagenotion image
输入：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 <= n <= 500
  • 500 <= Node.val <= 500
  • 1 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？
通过次数248,334提交次数450,599

法 1 暴力

思路
先找到要翻转的链表头节点，且将要翻转的链表尾部断开
翻转完成后再接上
题解
# 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:
        while left == right or head is None or head.next is None:
            return head
        dummy = ListNode(-1, head)
        cur = dummy
        i = 0
        while cur:
            if i + 1 == left:
                left = cur.next
                left_prev = cur

            elif i == right:
                right_next = cur.next
                # 将right 后面的切断
                cur.next = None
                break

            cur = cur.next
            i += 1

        # 翻转 left 为首的链表
        pre, cur = None, left
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        
        left_prev.next = pre
        left.next = right_next

        return dummy.next

法 2 原地翻转

思路
找到翻转位置后原地进行翻转，具体步骤如下：
  • 跳过left 个节点
  • 翻转right - left 个节点
  • 将两头链接起来
notion imagenotion image
题解
# 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:
        while left == right or head is None or head.next is None:
            return head

        dummy = ListNode(-1, head)
        cur, prev = head, dummy
        i = 1
        while i < left:
            prev = cur
            cur = cur.next
            i += 1
        # 保存下来， 
        # connect 是 翻转节点的前一个
        # tail是翻转后的尾巴
        connect = prev
        tail = cur
        # 翻转
        while i <= right:
            temp = cur.next
            cur.next = prev
            prev = cur
            cur = temp
            i += 1

        # 重新链接
        connect.next = prev
        tail.next = cur

        return dummy.next

法 3 插入法 直接插入

思路
使用插入法来执行交换操作。好处在于未用维护后面的节点
题解
# 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:
        if right == left or head is None:
            return head

        dummy = ListNode(-1, head)
        prev, cur = dummy, dummy

        idx = 0
        while idx <= right:
            prev = cur
            cur = cur.next
            idx += 1
            # 交换 right - left 次节点
            while right > idx >= left:
                idx += 1
                # 当前待插入节点
                temp = cur.next
                # 跨越待插入节点
                cur.next = temp.next
                # 执行插入操作
                temp.next = prev.next
                prev.next = temp

        return dummy.next