解题思路

  1. 暴力法 先遍历一遍链表获取链表的size ， size - n 得到的就是 应删除节点的前置节点 ， 如若这个前置节点为0 ，则应该删除头节点， 若不为0 直接删除 size - n 的next 节点
  2. 快慢指针法 设置快慢指针fast 和slow ， fast比slow 先走n个节点，当fast 为0时，slow 正处于 应删节点的前置节点， 我们直接删除 slow节点的 next节点就可以了

1. 暴力法

  1. /*
  2.  * @lc app=leetcode.cn id=19 lang=javascript
  3.  *
  4.  * [19] 删除链表的倒数第N个节点
  5.  */
  7. // @lc code=start
  8. /**
  9.  * Definition for singly-linked list.
  10.  * function ListNode(val) {
  11.  *     this.val = val;
  12.  *     this.next = null;
  13.  * }
  14.  */
  15. /**
  16.  * @param {ListNode} head
  17.  * @param {number} n
  18.  * @return {ListNode}
  19.  */
  20. var removeNthFromEnd = function (head, n) {
  21.   if (!head.next || !head) return null
  22.   let p = head
  23.   let size = 0
  24.   while (p) {
  25.     size++
  26.     p = p.next
  27.   }
  29.   if (n > size) return null
  31.   size = size - n
  33.   if (size == 0) {
  34.     return head.next
  35.   }
  37.   p = head
  38.   while (--size) {
  39.     p = p.next
  40.   }
  42.   const deleteNode = p.next
  44.   p.next = deleteNode.next
  46.   return head
  47. }
  • 时间复杂度为 O(n)
  • 空间复杂度为 O(1)

2. 快慢指针法

  1. /*
  2.  * @lc app=leetcode.cn id=19 lang=javascript
  3.  *
  4.  * [19] 删除链表的倒数第N个节点
  5.  */
  7. // @lc code=start
  8. /**
  9.  * Definition for singly-linked list.
  10.  * function ListNode(val) {
  11.  *     this.val = val;
  12.  *     this.next = null;
  13.  * }
  14.  */
  15. /**
  16.  * @param {ListNode} head
  17.  * @param {number} n
  18.  * @return {ListNode}
  19.  */
  20. var removeNthFromEnd = function (head, n) {
  21.   if (!head.next || !head) return null
  23.   let fast = (slow = head)
  24.   while (n--) {
  25.     fast = fast.next
  26.   }
  28.   if (!fast) return head.next
  30.   while (fast.next) {
  31.     fast = fast.next
  32.     slow = slow.next
  33.   }
  35.   const deleteNode = slow.next
  36.   slow.next = deleteNode.next
  37.   return head
  38. }
  39. // @lc code=end
  • 时间复杂度 O(n)
  • 空间复杂度 O(1)