[数据结构与算法]【LeetCode 单链表专项】反转链表II（92）

文章目录

• • 1. 题目
  • • 1.1 示例
    • 1.2 说明
    • 1.3 限制
    • 1.4 进阶
  • 2. 解法一（穿针引线）
  • • 2.1 分析
    • 2.2 解答
    • 2.3 复杂度
  • 3. 解法二（头插法）
  • • 3.1 解答
    • 3.2 分析
    • 3.3 复杂度

1. 题目

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

1.1 示例

• 示例 $1$ ：
  • 输入： 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 说明

• 来源： 力扣（LeetCode）
• 链接： https://leetcode-cn.com/problems/reverse-linked-list-ii

1.3 限制

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

1.4 进阶

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

2. 解法一（穿针引线）

2.1 分析

• 定位至需要进行节点反转的起始位置：
  需要注意的是，在通过迭代完成定位后，为了后续能够将反转的部分和未反转的部分连接起来（通过如下的最后一张图将知道此举的目的），需要记录此时整数 left 确定的节点及其左边相邻节点，这里分别用 left_node 和 prev_node 来表示。
  
• 使用迭代的方式进行节点反转：
  • 进行第一次迭代：
    
  • 进行第二次迭代：
    
  • 进行第三次迭代：
    
• 将未反转部分和已反转部分进行连接：
  需要注意的是，在完成上述节点反转之后及连接之前，需要和一开始一样记录整数 right 确定的节点及其右边相邻的节点，分别用 right_node 和 succ_node 来表示。
  

2.2 解答

from sys import maxsize


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, val: int):
        node = ListNode(val)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = self.tail.next


class Solution:
    def reverse_between(self, head: ListNode, left: int, right: int) -> ListNode:
        dummy = ListNode(maxsize)
        dummy.next = head
        predecessor, current = dummy, head
        for _ in range(left - 1):
            predecessor = current
            current = current.next
        prev_node, left_node = predecessor, current
        for _ in range(left - 1, right):
            successor = current.next
            current.next = predecessor
            predecessor = current
            current = successor
        right_node, succ_node = predecessor, current
        prev_node.next = right_node
        left_node.next = succ_node
        return dummy.next


def main():
    values = [1, 2, 3, 4, 5]
    linked_list = LinkedList()
    for value in values:
        linked_list.append(value)

    sln = Solution()
    reversed_head = sln.reverse_between(linked_list.head, 2, 4)

    cursor = reversed_head
    while cursor:
        print(cursor.val, end='\t')  # 1	4	3	2	5
        cursor = cursor.next


if __name__ == '__main__':
    main()

需要特别留意的是，这里使用了一个傀儡节点 dummy ，其 next 域指向 head 节点，这样做避免了讨论当待反转节点包括头节点的情况。

2.3 复杂度

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

3. 解法二（头插法）

3.1 解答

from sys import maxsize


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, val: int):
        node = ListNode(val)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = self.tail.next


class Solution:
    def reverse_between(self, head: ListNode, left: int, right: int) -> ListNode:
        dummy = ListNode(maxsize)
        dummy.next = head
        predecessor, current = dummy, head
        for _ in range(left - 1):
            predecessor = current
            current = current.next
        for _ in range(left, right):
            successor = current.next
            current.next = successor.next
            successor.next = predecessor.next
            predecessor.next = successor
        return dummy.next


def main():
    values = [1, 2, 3, 4, 5]
    linked_list = LinkedList()
    for value in values:
        linked_list.append(value)

    sln = Solution()
    reversed_head = sln.reverse_between(linked_list.head, 2, 4)

    cursor = reversed_head
    while cursor:
        print(cursor.val, end='\t')  # 1	4	3	2	5
        cursor = cursor.next


if __name__ == '__main__':
    main()

3.2 分析

3.3 复杂度

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