leetcode 75 - 2095. Delete the Middle Node of a Linked List

linked list ? - https://www.opentutorials.org/module/1335/8821

Linked list - Data Structure (자료구조)

 

처음 풀이 - linked list와 array list 를 구분하지 못함.

index로 접근하는 것이 비효율적이며 slice 메서드를 사용할 수 없음.

var deleteMiddle = function(head) {
    // middle index 구하기
    // 해당 index의 값 제외하기
    const middleIdx = Math.floor(head.length / 2)
    const firstHalf = head.slice(0, middleIdx)
    const lastHalf = head.slice(middleIdx + 1)

    return firstHalf.concat(lastHalf)
};

 

효율적인 알고리즘 - two pointer technique: O(n)

- slow pointer 는 .next

- fast pointer 는 .next.next
-> fast pointer가 마지막 노드를 탐색하는 시점에 slow pointer는 중간 노드를 탐색한다.

 

알고리즘 적용한 풀이

/**
 * Definition for singly-linked list.
//  * function ListNode(val, next) {
//  *     this.val = (val===undefined ? 0 : val)
//  *     this.next = (next===undefined ? null : next)
//  * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteMiddle = function(head) {
 if (!head || !head.next) {
        // Invalid input or the list has less than two nodes
        return null;
    }

    let slowPointer = head;
    let fastPointer = head;
    let prevNode = null;

    // Move the fast pointer twice as fast as the slow pointer
    while (fastPointer && fastPointer.next) {
        prevNode = slowPointer;
        slowPointer = slowPointer.next;
        fastPointer = fastPointer.next.next;
    }

    // Delete the middle node by updating the pointers
    prevNode.next = slowPointer.next;

    return head;
};