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

链接：19.删除链表的倒数第N个结点
难度：Medium
标签：链表、双指针
简介：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

题解 1 - c

• 编辑时间：2021-11-19
• 内存消耗：5.8MB
• 编程语言：c
• 解法介绍：遍历。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
        int sum = 0;
        struct ListNode* p = head;
        while (p) p = p->next, sum++;
        if (sum == 1 && n == 1) return NULL;
        int del_idx = sum - n;
        p = head;
        if (del_idx == 0) return p->next;
        while (--del_idx) p = p->next;
        p->next = p->next->next;
        return head;
}

题解 2 - typescript

• 编辑时间：2020-10-18
• 执行用时：92ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：快慢指针，快指针先走 n 个节点。

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let first: ListNode | null = head;
  let second: ListNode = dummy;
  for (let i = 0; i < n; i++) first = first?.next!;
  while (first !== null) {
    first = first.next;
    second = second?.next!;
  }
  second.next = second.next?.next!;
  return dummy.next;
}

题解 3 - typescript

• 编辑时间：2020-10-18
• 执行用时：96ms
• 内存消耗：40.1MB
• 编程语言：typescript
• 解法介绍：利用栈排序。

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  if (head === null) return null;
  const stack: ListNode[] = [];
  let temp: ListNode | null = head;
  while (temp !== null) {
    stack.push(temp);
    temp = temp.next;
  }
  if (stack.length === n) return head.next;
  while (n-- !== 0) {
    stack.pop();
  }
  const node = stack.pop()!;
  node.next = node.next!.next;
  return head;
}

题解 4 - javascript

• 编辑时间：2020-05-22
• 执行用时：64ms
• 内存消耗：33.5MB
• 编程语言：javascript
• 解法介绍：压栈后出栈。

/**
 * 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) {
  if (head === null || head.next === null) return null;
  let temp = head;
  const stack = [];
  while (temp !== null) {
    stack.push(temp);
    temp = temp.next;
  }
  if (n === stack.length) return head.next;
  stack.pop();
  let c = 0;
  while (++c !== n) {
    stack.pop();
  }
  const node = stack.pop();
  node.next = node.next.next;
  return head;
};

题解 5 - typescript

• 编辑时间：2021-03-06
• 执行用时：108ms
• 内存消耗：39.2MB
• 编程语言：typescript
• 解法介绍：假设总长 len,q 先走 n 步,还剩 len-n 步,p 从头开始和 q 一起走,走到 q 为 null 的时候,p 就是要删除的节点。

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummyHead = new ListNode(0, head);
  let q = head;
  while (n--) q = q!.next!;
  let p = dummyHead;
  while (q !== null) {
    q = q.next!;
    p = p.next!;
  }
  p.next = p.next!.next;
  return dummyHead.next;
}