[leetcode - Bliend-75 ] 19. 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.

给一个 linked list 并移除倒数第 n 个 node。

Example

Input: 1 -> 2 -> 3 -> 4 -> 5, n = 2;
Output: 1 -> 2 -> 3 -> 5

Step

利用快慢双指针，建立一个 node 连在 head 前面并让慢指针指向 node

设定慢指针与快指针

让快指针先跑 n 个 node，再让两个指针一起跑，跑到快指针抵达 head 的最后一个 node，这样就会使慢指针刚好停在要被移除的 node 的前一个 node。

将慢指针指到的 node 连接到下下个 node

Coding

/** * @param {ListNode} head * @param {number} n * @return {ListNode} */var removeNthFromEnd = function(head, n) {    if(head == null) return head;     var node = new ListNode(0);    node.next = head;    let slow = node;    let fast = head;    while (n > 0) {        fast = fast.next;        n--;    }    while(fast){        fast = fast.next;        slow = slow.next;    }    if(slow.next === null){        slow.next = null ;    } else {        slow.next = slow.next.next;    }    return node.next;};

Time complexity: O(n)