[leetcode / 92] Reverse Linked List II
in Problem Solving on leetcode
날짜: 2021년 8월 25일
카테고리: 연결 리스트
태그: Medium, 92, 파이썬
leetcode 92 - Reverse Linked List II
입출력 예시
| 예제 입력 | 예제 출력 |
|---|---|
| head = [1,2,3,4,5], left = 2, right = 4 | [1,4,3,2,5] |
| head = [5], left = 1, right = 1 | [5] |
코드
# 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 not head or left == right:
return head
linked_list = start = ListNode(None)
linked_list.next = head
for _ in range(left - 1):
start = start.next
end = start.next
for _ in range(right - left):
point = start.next
start.next = end.next
end.next = end.next.next
start.next.next = point
return linked_list.next
풀이 과정
빈 연결 리스트 거나 left와 right가 같을 경우 head를 반환하는 예외처리
linked_list와 start에 None 저장 후 linked_list를 head와 연결
left에 1을 뺀 값 만큼 start를 옆으로 시프트
end에는 start바로 다음 값을 저장
right에서 left를 뺀 값 에서 1을 더한 만큼 반복 (range()를 사용하여 구간의 값이기 때문에 +1)
point에start바로 다음 값을 저장start가 향하는 다음 값으로end의 다음 값을 저장end가 향하는 다음 값으로end의 다음 다음 값을 저장start의 다음 값이 향하는 다음 값으로point저장
이를 반복하여 구간의 연결 리스트를 뒤집은 후
linked_list의 다음 값을 출력 (linked_list는 연결 리스트 범위 밖 None이 저장되어 있기 때문)
