LeetCode题解19.removeNthNodeFromEndofList

题目地址

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description

题目描述

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

思路

双指针，指针A先移动n次， 指针B再开始移动。当A到达null的时候， 指针b的位置正好是倒数n

我们可以设想假设设定了双指针p和q的话，当q指向末尾的NULL，p与q之间相隔的元素个数为n时，那么删除掉p的下一个指针就完成了要求。

设置虚拟节点dummyHead指向head

设定双指针p和q，初始都指向虚拟节点dummyHead

移动q，直到p与q之间相隔的元素个数为n

同时移动p与q，直到q指向的为NULL

将p的下一个节点指向下下个节点

(图片来自： https://github.com/MisterBooo/LeetCodeAnimation)

关键点解析

1. 链表这种数据结构的特点和使用

2. 使用双指针

3. 使用一个dummyHead简化操作

代码

Support: JS, Java

• Javascript Implementation

/*
 * @lc app=leetcode id=19 lang=javascript
 *
 * [19] Remove Nth Node From End of List
 *
 * https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
 *
 * algorithms
 * Medium (34.03%)
 * Total Accepted:    360.1K
 * Total Submissions: 1.1M
 * Testcase Example:  '[1,2,3,4,5]\n2'
 *
 * Given a linked list, remove the n-th node from the end of list and return
 * its head.
 * 
 * Example:
 * 
 * 
 * Given linked list: 1->2->3->4->5, and n = 2.
 * 
 * After removing the second node from the end, the linked list becomes
 * 1->2->3->5.
 * 
 * 
 * Note:
 * 
 * Given n will always be valid.
 * 
 * Follow up:
 * 
 * Could you do this in one pass?
 * 
 */
/**
 * 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) {
  let i = -1;
  const noop = {
    next: null
  };

  const dummyHead = new ListNode(); // 增加一个dummyHead 简化操作
  dummyHead.next = head;

  let currentP1 = dummyHead;
  let currentP2 = dummyHead;

  
  while (currentP1) {

    if (i === n) {
      currentP2 = currentP2.next;
    }

    if (i !== n) {
        i++;
    }
    
    currentP1 = currentP1.next;
  }

  currentP2.next = ((currentP2 || noop).next || noop).next;

  return dummyHead.next;
};

• Java Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        TreeNode dummy = new TreeNode(0);
        dummy.next = head;
        TreeNode first = dummy;
        TreeNode second = dummy;

        if (int 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;
    }
}

LeetCode题解堆排序和快速排序

堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法，其中 n 为数据规模。 那么两者谁更快呢？ 为什么？题解：快排最坏情况下是O(n^2)，平均和最好是O(nlogn) ，堆排序始终为O(nlogn)，还是堆排序快吧

LeetCode题解斜着遍历

遍历是算法的基础。 我们平时看到的 DFS 和 BFS 都是搜索， 而搜索的核心就是遍历，而关键点就是遍历的方式。 从根本上说动态规划也是枚举所有的可能，而枚举就需要用到遍历。 而平时遍历一个二维数组 martrix 的时候， 我们习惯的方式是按行从左到右或者从右到左遍历。 少有情况是按照列遍历， 更少有情况是斜着遍历。那么这次就考考你， 怎么斜着遍历一个二…

LeetCode题解砝码的最小数量

假设有三种重量的砝码，2g、3g、7g，对于任意重量物品，请设计一个函数getResult(weight)，接收一个参数weight，返回所需砝码的最小数量。输入示例：const weight = 100;输出示例：getResult(weight) // 15 其中7g的14个，2g的1个题解：```phpfunction getResult($weigh…

如何告诉Checker遗留方法将接受Nullable类型？ - java

考虑一下：@Nullable Object obj = null; Optional<Object> optional = Optional.ofNullable(obj); 这会失败，因为检查器框架假定ofNullable无法接受null值（毕竟，其参数未标记为@Nullable）。有没有办法告诉Checker-framework这个方法（或我…

Spacy如何将标记标签整体化？ - python

在包含＃标签（例如tweet）的句子中，spacy的令牌生成器将标签分为两个令牌：import spacy nlp = spacy.load('en') doc = nlp(u'This is a #sentence.') [t for t in doc] 输出：[This, is, a, #, sentence, .…