zhangdi

19.删除链表的倒数第 N 个结点 ​

题目 ​

LeetCode 中等

题目

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

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

题解 ​

方法：取长度 ​

先取长度，再删除，O(L) O(1)

ts
function removeNthFromEnd(head: ListNode | null, k: number): ListNode | null {
  let len = 0
  let cur = head
  while (cur) {
    len++
    cur = cur.next
  }
  let ti = len - k + 1
  console.log('总长度：', len, '目标位置：', ti)
  let ci = 1
  cur = head
  while (cur) {
    //找目前的前一个，修改它的next
    if (ti - 1 === ci) {
      cur.next = cur.next.next
      return head
    }
    ci++
    cur = cur.next
  }
}

const list = new LinkedList([1, 2, 3, 4, 5])
console.log('🌰', removeNthFromEnd(list.head, 2))

方法：双指针 ​

双指针 O(L) O(1)

ts
function removeNthFromEndUseTwoPointers(
  head: ListNode | null,
  n: number,
): ListNode | null {
  let res = head
  let fast = res
  let slow = res
  while (fast.next) {
    //快指针先走n步
    n--
    fast = fast.next
    //慢指针开始走
    if (n < 0) {
      slow = slow.next
    }
  }
  //快停在最后一个，慢停在目标node的前一个
  console.log(n, 'slow', slow, 'fast', fast)
  slow.next = slow.next.next
  return res
}

const list2 = new LinkedList([1, 2, 3, 4, 5])
console.log('🌰', removeNthFromEndUseTwoPointers(list2.head, 2))

方法：栈 ​

栈 O(L) O(L)

ts
function removeNthFromEndUseStack(
  head: ListNode | null,
  n: number,
): ListNode | null {
  const res = head
  const stack = []
  let cur = res
  while (cur != null) {
    stack.push(cur)
    cur = cur.next
  }

  for (let i = 0; i < n; i++) {
    stack.pop()
  }

  let peek = stack[stack.length - 1]
  peek.next = peek.next.next
  return res
}

const list3 = new LinkedList([1, 2, 3, 4, 5])
console.log('🌰', removeNthFromEndUseStack(list3.head, 2))