关于javascript:19-删除链表的倒数第-N-个结点LeetCodeC语言及JS实现

一、C 语言实现

1. 先获取链表长度，再从正向遍历

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
// 比拟奢侈的算法
// 先求出链表长度，而后依据长度求出要删除的元素正向的地位
// 最初遍历到该元素前一元素进行删除操作

struct ListNode *removeNthFromEnd(struct ListNode *head, int n)
{
  int len = 0;
  struct ListNode *origin = head; 
  // 计算链表的长度
  while (head)
  {
    len++;
    head = head -> next;
  }
  // 将 head 从新指向头结点
  head = origin;
  // 计算是正向第几个节点
  int count = len - n;
  // 如果是正向第一个结点，则头结点被删除，只须要间接返回头结点的 next 即可
  if (count == 0) {return head -> next;} 
  // 如果不是正向第一个结点（即结点），则间接遍历到该结点的前一个结点
  for (int i = 0; i < count - 1; i++) {head = head -> next;}
  // 将该节点删除，而后返回头结点的指针
  head -> next = head -> next -> next;
  return origin;
}

2. 双指针法，只须要遍历一次

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//  双指针法，挪动 first 指针使其到的链表末端，同时挪动 second 指针
//  使其指向最终要删除的节点的前一个节点，此时即可删除节点并返回头结点
//  只需一轮循环即可实现
struct ListNode *removeNthFromEnd(struct ListNode *head, int n)
{
  // 创立一个哑结点，并将其指向头结点
  struct ListNode dumpy = {0, head};
  // 将 first 指针指向 head 头指针
  struct ListNode *first = head;
  // 将 second 指针指向哑结点，此处 dumpy 是构造体，因而须要取地址
  struct ListNode *second = &dumpy;
  for (int i = 0; i < n; i++)
  {first = first->next;}
  while (first)
  {
    first = first->next;
    second = second->next;
  }
  second->next = second->next->next;
  // first second 和 head 都是构造体指针，因而能够应用 -> 拜访成员
  // dumpy 是构造体，能够间接用点号拜访
  return dumpy.next;
}

二、JS 实现

1. 先获取链表长度，再从正向遍历

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
// 比拟奢侈的算法
// 先求出链表长度，而后依据长度求出要删除的元素正向的地位
// 最初遍历到该元素前一元素进行删除操作
const removeNthFromEnd = function (head, n) {
  const origin = head
  if (!head) {return null}
  let count = 1
  while (head.next) {
    count++
    head = head.next
  }
  head = origin
  if (count <= n) {return origin.next} else {
    // 倒数第 n 个数，就是负数第 count - n + 1 个数，那么，只须要遍历到此数的前一个数，即可
    // 前一个数则是第 count - n 个数，从第一个数开始遍历，只需遍历 count - n - 1 次就可达到此数
    const index = count - n - 1
    for (let i = 0; i < index; i++) {head = head.next}
    head.next = head.next.next
  }
  return origin
}

2. 双指针法，只须要遍历一次

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */

//  双指针法，挪动 first 指针使其到的链表末端，同时挪动 second 指针
//  使其指向最终要删除的节点的前一个节点，此时即可删除节点并返回头结点
//  只需一轮循环即可实现
const removeNthFromEnd = function (head, n) {
  // 创立一个哑结点，并将它指向头结点
  const dumpy = new ListNode(0, head)
  // 将第二个指针指向哑结点，第一个指针指向头结点
  let second = dumpy
  let first = head
  // 将第一个指针往前挪动 n 个地位
  for (let i = 0; i < n; i++) {first = first.next}
  // 挪动第一个指针直到链表结尾，同时挪动第二个指针
  while (first) {
    first = first.next
    second = second.next
  }
  // 此时第二个指针指向的是倒数第 n 个节点的前一个节点
  // 将倒数第 n 个节点删除即可
  second.next = second.next.next
  // 返回头结点，应用 head 会出错，为什么呢？因为如果要删除的节点是头结点，那么头结点被删除后，// 哑结点间接指向第二个结点，而 head 还是指向头结点，因而会报错。// 所以此时要么返回 head.next，要么返回 dumpy.next。// 而 head.next 的返回须要判断 second.next 是不是指向头结点
  // 而 dumpy.next 则间接应用
  return dumpy.next
}

三、算法工夫及空间复杂度

1. 链表长度法的工夫及空间复杂度

• 工夫复杂度：O(L)，其中 L 是链表的长度。
• 空间复杂度：O(1)。

2. 双指针法

• 工夫复杂度：O(L)，其中 L 是链表的长度。
• 空间复杂度：O(1)。