LeetCode

Appearance

92. Reverse Linked List II ​

题目 ​

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

 

Constraints:

  • The number of nodes in the list is n.
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

 

Follow up: Could you do it in one pass?
Related Topics
  • 链表

  • 👍 1974
  • 👎 0

    • 思路 ​

    • 本题反转链表 A - B - C，可以简化为找到 A 的末节点和C 的首节点，连接反转 B,
    • 反转链表范围可能包含 head 节点，需要使用 dummy 虚拟节点
    • 首先 A 末节点，位置为 left - 1
    • 反转链表的开始反转节点为 left, 此节点是后续相连到C 首节点
    • 反转链表的结束节点为 right, 此节点是后续相连到 A的末尾节点
    • 反转链表结束时，使用 pre 作为新节点的头，则 cur 节点为C 段的首节点

    解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
# 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]:
        dummy = ListNode(0, head)

        left_head = dummy

        # 寻找 left 的前一个元素，作为反转子链的左边 head 连接点
        for i in range(left - 1):
            left_head = left_head.next

        right_head = left_head.next
        cur = right_head
        pre = None

        # 反转 left - right 的链表
        # 反转结束后，pre 为反转后链表的头部， cur 为遗留链表的头部
        for i in range(left, right + 1):
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp

        left_head.next = pre
        right_head.next = cur

        return dummy.next



        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(right)
    • 空间复杂度 O(1)