删除链表的倒数第N个节点(JS版本)

2. 思路：

先实现一个单向链表

// 节点
function Node(value) {
  this.value = value; // 当前节点的元素
  this.next = null; // 下一个节点的链接
}

// 查找给定节点位置
function find(item) {
  let curNode = this.head;
  while (curNode.value !== item) {
    curNode = curNode.next;
  }
  return curNode;
}
// 插入节点
function insert(value, preValue) {
  const newValue = new Node(value);
  const curNode = this.find(preValue);
  newValue.next = curNode.next;
  curNode.next = newValue;
}


function SList() {
  this.head = new Node('head'); // 头节点
  this.find = find;
  this.insert = insert;
}


const list = new SList();


list.insert('1', 'head');
list.insert('2', '1');
list.insert('3', '2');
list.insert('4', '3');
list.insert('5', '4');
console.log(list);
复制代码

3. 单项链表

head -> 1 -> 2 -> 3 -> 4 -> 5
复制代码

4. 代码实现题目要求

• 思路
  • 让前面的指针先移动n步，之后前后指针共同移动直到前面的指针到尾部为止
  • 前指针为 start ，后指针为 end ，二者都等于 head
  • start 先向前移动 n 步
  • 之后 start 和 end 共同向前移动，此时二者的距离为 n ，当 start 到尾部时， end 的位置恰好为倒数第 n 个节点
  • 因为要删除该节点，所以要移动到该节点的前一个才能删除，所以循环结束条件为 start.next != null
  • 删除后返回 head.next ，为什么不直接返回 head 呢，因为 head 有可能是被删掉的点
  • 时间复杂度： O(n)

const removeNthFromEnd = function (head, n) {
  if (head === null || n === 0) return head;
  let start = head;
  let end = head;
  while (n > 0) {
    start = start.next;
    n--;
  }
  // 如果start为空，删除首部head
  if (start === null) {
    return head.next;
  }
  while (start.next != null) {
    start = start.next;
    end = end.next;
  }
  // 删除
  end.next = end.next.next;
  return head;
};
复制代码

5. 执行代码

const res = removeNthFromEnd(list.head, 2);
console.log(res);
复制代码

6. 执行过程

end = 0     1    2   3
start = 2   3    4   5 
找到3节点，end.next = end.next.next
替换4节点，也就是删除了
复制代码