Daily LeetCode Challenge - 2095. Delete the Middle Node of a Linked List

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

오늘 문제는 LinkedList 를 활용한 문제로 리스트 중간에 있는 node 를 삭제한 뒤 반환하는 문제였다.

중간에 있는 node 는 LinkedList 의 총 길이의 절반인 부분으로 중간의 위치를 구하는게 이 문제의 핵심이었다.

Two Pointer 알고리즘을 사용하여 중간지점을 구했는데,
첫번째 포인터는 한번에 한칸씩 전진시키고, 두번째 포인터는 한번에 두칸씩 전진시켜서,
두번째 포인터가 끝에 도달하면 첫번째 포인터는 중간지점을 가리킬 수 있게 하였다.

그렇게 첫번째 포인터가 중간지점에 도착하면, 중간지점에서 다음 노드를 끌어와서 중간지점에 삽입하여 해당 노드가 사라질 수 있도록 하였다.

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun deleteMiddle(head: ListNode?): ListNode? {
        
        if(head!!.next == null) return null
        
        findMiddle(head, head?.next?.next)
        
        return head
    }
    
    private fun findMiddle(head : ListNode?, pointTwo : ListNode?) {
        
        if(pointTwo?.next == null) {
            head!!.next = head!!.next?.next
            return
        }
        
        findMiddle(head?.next, pointTwo?.next?.next)
    }
}

해당 알고리즘의 시간복잡도는 O(N) 으로 중간지점을 구하거나, 특정 위치를 반복적으로 참조해야 할 때는 Two Pointer 알고리즘을 사용하면 편한것 같다.