리트코드 2095. Delete the Middle Node of a Linked List

https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/

 

이 문제는 연결 리스트(linked list)에서 중간 노드를 삭제하는 문제이다. 중간 노드는 n개의 노드가 있을 때 ⌊n / 2⌋번째 노드이다.

문제를 해결하기 위한 접근 방법은 다음과 같습니다:

접근 방법

1. 리스트 길이 계산: 먼저, 연결 리스트를 순회하면서 전체 길이 n을 계산한다.
2. 중간 노드 위치 계산: 중간 노드의 인덱스는 ⌊n/2⌋로 계산한다.
3. 중간 노드 삭제:
   • 만약 중간 노드가 첫 번째 노드라면 (즉, n이 1이라면), 리스트의 head를 다음 노드로 바꾼다.
   • 중간 노드가 다른 위치에 있다면, 리스트를 다시 순회하면서 중간 노드의 바로 전 노드를 찾은 다음, 그 노드의 next 포인터를 중간 노드의 다음 노드로 변경한다.
4. 결과 반환: 변경된 연결 리스트의 head를 반환한다.

# 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]:
        n = 0
        current = head
        while current:
            n += 1
            current = current.next

        mid = n // 2
        current = head

        if n == 1:
            return None

        for _ in range(mid - 1):
            current = current.next
        current.next = current.next.next

        return head