leetcode19-删除链表的倒数第N个节点

原题

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

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

解法

思想

使用两个指针,让快指针一开始和慢指针保持n的距离,两者一起以同样速度移动,则当快指针指向链表的最后一个节点的时候,慢指针的下一个节点就是要删除的节点。

代码

HashSet:

/**
 * 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) {
        ListNode slow;
        ListNode fast;
        slow = fast = head;
        for(int i = 0;i<n;i++){
            fast = fast.next;
        }
        //这种情况需要删除头节点
        if(fast == null) return head.next;
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return head;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode19-%e5%88%a0%e9%99%a4%e9%93%be%e8%a1%a8%e7%9a%84%e5%80%92%e6%95%b0%e7%ac%acn%e4%b8%aa%e8%8a%82%e7%82%b9/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月14日
下一篇 2019年12月16日

相关推荐

  • leetcode328-奇偶链表

    原题 给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空…

    算法 2019年12月16日
    0130
  • leetcode106-从中序与后序遍历序列构造二叉树

    原题 根据一棵树的中序遍历与后序遍历构造二叉树。 注意:你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postor…

    算法 2020年1月13日
    0380
  • leetcode611-有效三角形的个数

    原题 给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。 示例1: 输入: [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用…

    2020年2月8日
    060
  • leetcode110-平衡二叉树

    原题 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1:  给定二叉树 […

    算法 2020年1月17日
    0170
  • leetcode112-路径总和

    原题 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例:  给定如下二叉树,…

    算法 2020年1月12日
    0140
  • leetcode3-无重复字符的最长子串

    原题 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长…

    2019年12月26日
    0100
  • leetcode31-下一个排列

    原题 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1…

    算法 2022年4月13日
    02363
  • leetcode8-字符串转换整数 (atoi)

    原题 请你来实现一个 atoi 函数,使其能将字符串转换成整数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下: 如果第一个…

    算法 2020年4月3日
    0270
  • leetcode142-环形链表II

    原题 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始…

    2019年12月14日
    0420
  • leetcode1371-每个元音包含偶数次的最长子字符串

    原题 给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 'a','e','i','o','u' ,在子字符串中都恰好出现了偶数次。 示例 1: 输入…

    算法 2020年5月20日
    01540

发表回复

登录后才能评论