•
문제 설명 : 제공된 연결리스트의 첫 노드만을 사용하여, 전체 연결 리스트 중 중간 노드를 제외한 후 첫 노드를 반환
•
풀이 방법
◦
이 문제는 전체 길이를 바로 확인할 수 없다.
▪
결국에는 순회를 하여 중간노드를 찾아야한다.
◦
하지만, 전체 길이를 알아내기위한 순회와 절반 길이만큼 순회 2번이 이루어지면 시간 복잡도에서 손해이다.
▪
이를 위해, Two Pointer 방법 중 “토끼와 거북이 알고리즘” 방식을 사용한다.
▪
1회 탐색 시, 이동 거리가 2배 차이나는 2개의 포인터를 사용한다.
•
2개씩 이동하는 포인터 → 가장 마지막까지 이동
•
1개씩 이동하는 포인터 → 절반까지만 이동
◦
중간 노드를 알아내는게 아니고, 삭제를 해야하기 때문에 “삭제해야하는 중간노드” 를 next 로 가지고 있는 직전 Node까지만 이동해야한다.
◦
이를 위해서 중간 직전 노드인지 확인하는 조건문을 추가한다.
•
시간복잡도 : → 정확하게는
•
성공 코드
# 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]:
left, right = head, head
result = []
if head.next == None:
return None
while left != None:
# left가 중간 노드에 도달하기 직전인지 확인
if right.next.next == None or right.next.next.next == None:
left.next = left.next.next
break
# left는 하나씩, right는 2개씩 이동한다.
# right가 연결 리스트의 마지막노드 혹은 그 이상 도달한 순간, left는 중간 노드에 위치한다.
left = left.next
right = right.next.next
return head
Python
복사