연결된 목록의 중간 노드 삭제

연결된 목록의 head가 제공됩니다. 중간 노드를 삭제하고 수정된 연결 리스트의 head를 반환합니다.

크기가 n인 연결 목록의 중간 노드는 0 기반 인덱싱을 사용하는 시작부터 ⌊n / 2⌋th 노드입니다. 여기서 ⌊x⌋는 x보다 작거나 같은 가장 큰 정수를 나타냅니다.

n = 1 , 2 , 3 , 4 및 5 의 경우 중간 노드는 0 , 1 , 1 , 2 및 2 각각.

예 1:



입력: 헤드 = [1,3,4,7,1,2,6]
출력: [1,3,4,1,2,6]
설명:
위의 그림은 주어진 연결 리스트를 나타냅니다. 노드의 인덱스는 다음과 같습니다.
n = 7이므로 값이 7인 노드 3이 중간 노드이며 빨간색으로 표시됩니다.
이 노드를 제거한 후 새 목록을 반환합니다.

예 2:



입력: 헤드 = [1,2,3,4]
출력: [1,2,4]
설명:
위의 그림은 주어진 연결 리스트를 나타냅니다.
n = 4인 경우 값이 3인 노드 2는 빨간색으로 표시된 중간 노드입니다.

예 3:



입력: 헤드 = [2,1]
출력: [2]
설명:
위의 그림은 주어진 연결 리스트를 나타냅니다.
n = 2인 경우 값이 1인 노드 1이 빨간색으로 표시된 중간 노드입니다.
값이 2인 노드 0은 노드 1을 제거한 후 남은 유일한 노드입니다.

제약:

목록의 노드 수가 [1, 105] 범위에 있습니다.

1 <= Node.val <= 105

해결책:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        prev = slow
        fast = head
        n = 0
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
            n += 1
        if n == 0:
            return None
        prev.next = slow.next
        return head