Pengjielee's blog

题目

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

示例 1：
1 -> 2 -> 3 -> 4 -> 5

//删除倒数第2个后：
1 -> 2 -> 3 -> 5

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

1、暴力求解法

如链表：1 -> 2 -> 3 -> 4 -> 5
链表的长度：L = 5；
删除倒数第2个：设n = 2，即删除节点4；
也就是删除正数第4个(设为m)，(m = L-n+1 = 5-2+1 = 4)；

结论：删除倒数第n个节点，即删除正数 L-n+1 的节点。

/**
 * 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) {
  // 获取链表长度
  const getLength = (head) => {
    let length = 0;
    while(head != null){
      length++;
      head = head.next;
    }
    return length;
  }

  const length = getLength(head);

  // 设置哑节点，方便删除
  const dummy = new ListNode(0);
  dummy.next = head;

  let curr = dummy;
  // m,正数要删除的节点
  const m = length - n + 1;

  // 举例说明：
  // 原链表：1 -> 2 -> 3 -> 4 -> 5 (链表长度L=5)
  // 要删除n = 2, 则 m = L-n+1 = 5-2+1 = 4 
  // 添加哑节点后：0 -> 1 -> 2 -> 3 -> 4 -> 5
  // i要走到3，i要走3步( 1 < i < 4)

  // 注意：i从1开始
  for(let i = 1; i < m; i++){
    curr = curr.next;
  }
  curr.next = curr.next.next;
  return dummy.next;
};

2、双指针

// n = 2
// 1 -> 2 -> 3 -> 4 -> 5
//
// f         f'             f''
// 0 -> 1 -> 2 -> 3 -> 4 -> 5
// s              s''
var removeNthFromEnd = function(head, n) {
  // 设置哑节点，方便删除
  const dummy = new ListNode(0);
  dummy.next = head;

  // 设置快指针
  let fast = head;
  // 设置慢指针
  let slow = dummy;
  // 快指针先走n步
  for(let i = 0; i < n; i++){
    fast = fast.next;
  }
  // 快慢指针一起走
  while(fast){
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return dummy.next;
};

测试数据：

function ListNode(val) {
  this.val = val;
  this.next = null;
}
// 1 -> 2 -> 3 -> 4 -> 5
var node1 = new ListNode(1);
var node2 = new ListNode(2);
var node3 = new ListNode(3);
var node4 = new ListNode(4);
var node5 = new ListNode(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;