题目描述

原题链接

示例 1：

输入：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

个人解法

JavaScript

解法1

两次扫描

/*
 * @lc app=leetcode.cn id=19 lang=javascript
 *
 * [19] 删除链表的倒数第 N 个结点
 */
// @lc code=start
/**
 * 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}
 */
 var removeNthFromEnd = function (head, n) {
  let len = 0;
  let temp = head;
  while (temp) {
    temp = temp.next;
    len++;
  }
  const target = len - n;
  if (target === 0) {
    return head.next;
  }
  temp = head;
  for (let i = 0; i < target - 1; i++) {
    temp = temp.next;
  }
  temp.next = temp.next.next;
  return head;
};
// @lc code=end

解法2

1次扫描

/*
 * @lc app=leetcode.cn id=19 lang=javascript
 *
 * [19] 删除链表的倒数第 N 个结点
 */
// @lc code=start
/**
 * 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}
 */
var removeNthFromEnd = function (head, n) {
  let len = 0;
  let temp = head;
  const arr = [];
  while (temp) {
    arr.push(temp);
    temp = temp.next;
    len++;
  }
  const target = len - n;
  if (target === 0) {
    return head.next;
  }
  temp = arr[target - 1];
  temp.next = temp.next.next;
  return head;
};
// @lc code=end

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p = head;
        int count = 1;
        while (p.next != null) {
            p = p.next;
            count++;
        }
        p = head;
        if (count == n) {
            head = p.next;
        } else {
            for (int i = 0; i < count - n-1; i++) {
                p = p.next;
            }
            p.next = p.next.next;
        }
        return head;
    }
}

其他解法

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode ln1 = new ListNode(-1, head);
        ListNode p = ln1,q=ln1;
        for (int i=0;i<n;i++){
            q = q.next;
        }
        while (q.next != null) {
            p=p.next;
            q=q.next;
        }
        if (p.next==head) {
            head=head.next;
        } else {
            p.next = p.next.next;
        }
        return head;
    }
}

JavaScript

/*
 * @lc app=leetcode.cn id=19 lang=javascript
 *
 * [19] 删除链表的倒数第 N 个结点
 */
// @lc code=start
/**
 * 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}
 */
var removeNthFromEnd = function(head, n) {
    let ret = new ListNode(0, head),
        slow = fast = ret;
    while(n--) fast = fast.next;
    if(!fast) return ret.next;
    while (fast.next) {
        fast = fast.next; 
        slow = slow.next
    };
    slow.next = slow.next.next;
    return ret.next;
};
// @lc code=end