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?
给定一个链表,只反转指定部分,如给定起始位置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