연결된 목록의 중간 노드 삭제

4031 단어 javascriptleetcode
연결된 목록의 헤드가 주어집니다. 중간 노드를 삭제하고 수정된 연결 목록의 헤드를 반환합니다.

크기가 n인 연결 목록의 중간 노드는 0 기반 인덱싱을 사용하여 처음부터 ⌊n/2⌋번째 노드입니다. 여기서 ⌊x⌋는 x보다 작거나 같은 가장 큰 정수를 나타냅니다.

n = 1, 2, 3, 4 및 5인 경우 중간 노드는 각각 0, 1, 1, 2 및 2입니다.

예 1:
입력: 헤드 = [1,3,4,7,1,2,6]
출력: [1,3,4,1,2,6]
설명:
위의 그림은 주어진 연결 리스트를 나타냅니다. 노드의 인덱스는 다음과 같습니다.
n = 7이므로 값이 7인 노드 3이 중간 노드이며 빨간색으로 표시됩니다.
이 노드를 제거한 후 새 목록을 반환합니다.

예 2:
입력: 헤드 = [1,2,3,4]
출력: [1,2,4]
설명:
위의 그림은 주어진 연결 리스트를 나타냅니다.
n = 4인 경우 값이 3인 노드 2는 빨간색으로 표시된 중간 노드입니다.

예 3:
입력: 헤드 = [2,1]
출력: [2]
설명:
위의 그림은 주어진 연결 리스트를 나타냅니다.
n = 2인 경우 값이 1인 노드 1이 빨간색으로 표시된 중간 노드입니다.
값이 2인 노드 0은 노드 1을 제거한 후 남은 유일한 노드입니다.

/**
 * 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) {
  let fast = head;
    let slow = head;
    let dummy = new ListNode(); //to deal with edge case that we need to delete the head node
    dummy.next = head;

    let prev = dummy;

    //both pointers travel
    while(fast && fast.next){
        fast = fast.next.next;
        prev = slow;
        slow = slow.next;
    }

    //delete the node
    while(slow.next){
        slow.val = slow.next.val;
        prev = slow;
        slow = slow.next;
    }

    prev.next = null;
    return dummy.next;
};

좋은 웹페이지 즐겨찾기