all articles

leetcode war 19 - Remove Nth Node From End of List

2017-10-07 @sunderls

leetCode js

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

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

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note: Given n will always be valid. Try to do this in one pass.

analysis

this seems a fairly easy task. For a liked list, we cannot know the length until we finish the traversing.

so, we keep a pointer to target node and use 3 pointers, keep the target node and the one before.

to make things easier, we add a start node.

trial 1 - three cursors

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    // append a new head
    var start = {
        next: head
    };

    var cursor = head;
    var prev = start;
    var target = head;
    var step = n;

    // cursor starts from head
    while (cursor) {
        // we try waiting some steps before moving prev & start
        // cursor & target starts ad the same
        // so we wait step goes to 0 and -1 for each round
        if (step === 0) {
            prev = prev.next;
            target = target.next;
        } else {
            step -= 1;
        }

        cursor = cursor.next;
    }

    prev.next = target.next;

    return start.next;
};

it passed, ranking top 40%, neither good or bad