[leetcode] 2095. Delete the Middle Node of a Linked List 파이썬 코드

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

 

중간 노드를 삭제한 연결 리스트를 반환하는 문제다. 

 

연결 리스트에서 중간 노드를 반환하는 건 slow, fast 이렇게 두 개의 포인터를 쓰면 된다. 

그런데 이 문제에서는 중간 노드를 제거해야 한다. 

 

연결리스트에서는 종종 head 앞에 가상의 노드를 하나 더 추가하면 쉽게 문제를 풀 수 있다.

dummy 노드를 만들어준다.

dummy = ListNode(next=head)

 

그런 다음에 slow 포인터를 dummy에 놓고, fast 포인터를 head에 놓는다.

slow, fast = dummy, head

 

leetcode 876번 중간 노드 찾기 문제에서는 slow, fast 둘 다 head에 놓았다.

그런데 slow를 dummy에, fast를 head에 놓으면,

fast가 노드를 전부 traverse하고 밖으로 나왔을 때 slow가 중간 노드 바로 이전 노드를 가리키게 된다. 

 

중간 노드를 삭제해야 하니까 

slow.next = slow.next.next

 

이렇게 하면 된다. 

 

dummy.next를 반환하면 중간 노드가 삭제된 연결리스트의 head를 반환하게 된다. 

 

class Solution(object):
    def deleteMiddle(self, head):
        dummy = ListNode(next=head)
        slow, fast = dummy, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        slow.next = slow.next.next

        return dummy.next

 

 

참고

https://algo.monster/liteproblems/2095