LeetCode 92. Reverse Linked List II - 链表(Linked List)系列题8

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:

LeetCode 92. Reverse Linked List II - 链表(Linked List)系列题8

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?

给定一个链表,只反转指定部分,如给定起始位置left和终止位置right,要求只反转从left到right之间(包含left和right)的节点。并且要求只能遍历一次链表。

这题要是left=1,right=n那就变成LeetCode 206. Reverse Linked List了,因此解题思路类似,可以用两个指针对[left, right]范围内的节点做反转操作。关键点是确定起始和终止位置,以及处理完后跟前后节点的链接。

可以用一个位置计数变量从1开始,定义两个指针pre和cur,当前指针cur从链表头开始,当计数到达left时当前指针指向的节点就是要处理的第一个节点,这时暂存当前节点start=cur及其父节点pre以备后用,另外再定义一个指针end指向当前节点的子节点,然后开始挨个进行反转操作,直到位置计数等于right终止,此时的当前指针cur指向的是区间的最后一个节点,end指向的是区间最后一个节点的next。最后利用个指针pre, start, cur和end把反转后的区间部分链接回原链表。

# 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 left == right:
            return head
        
        preHead = ListNode(-1, head)
        
        pre, cur = preHead, head
        pos = 1
        while pos < left:
            pre = cur
            cur = cur.next
            pos += 1
        
        start = cur
        end = cur.next
        while pos < right:
            tmp = end.next
            end.next = cur
            cur = end
            end = tmp
            pos += 1
        
        pre.next = cur
        start.next = end
        
        return preHead.next

上一篇:ROS2入门教程—创建ROS2工作空间


下一篇:关于Ubuntu20.04成功安装ROS2