LeetCode 솔루션 분류
[7/21] 92. Reverse Linked List II
본문
Medium
6637309Add to ListShareGiven 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?
Accepted
505,565
Submissions
1,153,545
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 47 ms, faster than 55.30% of Python3 online submissions for Reverse Linked List II.
Memory Usage: 14 MB, less than 87.01% of Python3 online submissions for Reverse Linked List II.
Memory Usage: 14 MB, less than 87.01% of Python3 online submissions for Reverse Linked List II.
# 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
i = 1
sub_prev = ListNode(0,head)
sub_tail = sub_head = head
while i < left:
sub_prev = sub_prev.next
sub_tail = sub_tail.next
sub_head = sub_head.next
i+=1
while i < right:
sub_tail = sub_tail.next
i+=1
sub_next = sub_tail.next
# reverse sub linked list
prev, curr, nxt = None, sub_head, sub_head.next
while curr != sub_next:
curr.next = prev
prev = curr
curr = nxt
nxt = nxt.next if curr else None
sub_prev.next = sub_tail
sub_head.next = sub_next
return head if left > 1 else sub_tail