LeetCode 솔루션

[7/21] 92. Reverse Linked List II

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.07.20 19:14

11,087 조회
1 댓글
0 추천
0 비추천
목록

글검색

게시글 쓰기

Medium

6637309Add to ListShare

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?

Accepted

505,565

Submissions

1,153,545

#Amazon, #Facebook, #Microsoft, #Google, #Apple

링크

https://leetcode.com/problems/reverse-linked-list-ii/ 3267 회 연결

익명
작성일 2022.07.20 19:15

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.

# 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

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.
[code=Python 3]# 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 [/code]