19. Remove Nth Node From End of List

Difficulty:
Related Topics:
Similar Questions:

    Problem

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

    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.

    Follow up:

    Could you do this in one pass?

    Solution

    /**
     * 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) {
      var h = new ListNode(0);
      var ll = h;
      var rr = h;
    
      h.next = head;
    
      for (var i = 0; i < n + 1; i++) {
        rr = rr.next;
      }
    
      while (rr !== null) {
        ll = ll.next;
        rr= rr.next;
      }
    
      ll.next = ll.next.next;
    
      return h.next;
    };
    

    Explain:

    1. 两个指针 a, b,初始都指向开头
    2. b 指针往后移动,直到两指针的位置相差 n
    3. 同时移动两指针,直到 b 指针到了最后。这时候因为两指针的位置相差 na 指针的位置就是从后面数第 n+1
    4. a 指针那里删掉后面一个,即第 n

    要注意可能会出现删掉 head 的情况。

    Complexity: