星星博客 »  > 

19、删除链表的倒数第n个节点

描述

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param n int整型 
  * @return ListNode类
  */
/* 1.设置两个遍历指针,第一个指针先遍历k个节点,两个指针再同时遍历
   2. 当第一个指针为空时,第二个指针指向倒数第k个节点
   3. 为了删除倒数第k个节点,还需设置一个指向该节点前驱的指针
*/
function removeNthFromEnd( head ,  n ) {
    if(!head) return head;
    let p1 = head;
    let p2 = head;
    let pre = null;
    //1. 第一个指针先遍历n个节点
    for(let i=0; i< n && p1; i++){
        p1 = p1.next;
    }
    //2. n等于链表长度,正好删除第一个节点
    if(p1 == null) { 
        return head.next;
    } 
    //3. 寻找倒数第k个结点
    while(p1!=null){
        p1 = p1.next;
        pre = p2;
        p2 = p2.next;
    }
    // 4. 删除p2指向的倒数第k个节点
    pre.next = p2.next;
    return head;
}
module.exports = {
    removeNthFromEnd : removeNthFromEnd
};

 

相关文章