19. Remove Nth Node From End of List

Leetcode

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

題目

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

解答

• 方法一

hashmap

var removeNthFromEnd = function(head, n) {
    // 只有一個元素的狀況，刪掉一個等於 null
    if(!head.next) return null;
    
    const map = new Map();
    
    let i = 1;
    let pointer = head;
    while(head) {
        map.set(i, head);
        i++;
        head = head.next;
    }
    const lastNode = map.get(i-n-1);
    if (lastNode) {
        lastNode.next = lastNode.next.next;
        return pointer;
    } else {
        // lastNode 不存在，代表要刪掉的是第一個元素
        return pointer.next;
    }
};

Runtime: 139 ms, faster than 6.81% of JavaScript online submissions for Remove Nth Node From End of List.

Memory Usage: 39.4 MB, less than 98.63% of JavaScript online submissions for Remove Nth Node From End of List.

• 方法二

Two pass algorithm

var removeNthFromEnd = function(head, n) {
    if(!head.next) return null;
    
    let i = 0;
    let pointer = head;
    while(head) {
        i++;
        head = head.next;
    }
    i = i - n - 1;
    head = pointer;
    
    // 代表要刪掉的是第一個元素
    if(i<0) return pointer.next;
    while(i) {
        head = head.next;
        i--;
    }
    head.next = head.next.next;
    
    return pointer;
};

Runtime: 80 ms, faster than 67.89% of JavaScript online submissions for Remove Nth Node From End of List.

Memory Usage: 40.1 MB, less than 72.75% of JavaScript online submissions for Remove Nth Node From End of List.

• 方法三

One pass algorithm

firstNode 先往前走，等到 firstNode 走到 n 的位置，secondNode 再跟 firstNode 一起走，等到 firstNode 走到底時，secondNode 即是我們要找的位置

var removeNthFromEnd = function(head, n) {
    let first = head;
    let second = head;
    
    let i = 0;
    while(first) {
        // 當 firstNode 走到超過 n 時，secondNode 再一起往前走
        if(i > n) {
            second = second.next;
        }
        first = first.next;
        i++
    }
    // 代表要刪掉的是第一個元素
    if(i===n) return head.next;
    second.next = second.next.next;
    
    return head;
};

Runtime: 97 ms, faster than 30.13% of JavaScript online submissions for Remove Nth Node From End of List.

Memory Usage: 39.8 MB, less than 86.38% of JavaScript online submissions for Remove Nth Node From End of List.