【链表问题】删除单链表中的第K个节点

前言

以专题的形式更新刷题贴,欢迎跟我一起学习刷题。每道题会提供简单的解答。

【题目描述】

在单链表中删除倒数第 K 个节点。

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1)

【难度

【解答】

删除的时候会出现三种情况:

1、不存在倒数第 K 个节点,此时不用删除。

2、倒数第 K 个节点就是第一个节点。

3、倒数第 K 个节点在第一个节点之后。

所以我们可以用一个变量 num 记录链表一共有多少个节点。

如果 num < K,则属于第一种情况。

如果 num == K,则属于第二中情况。

如果 num > K, 则属于第三种情况,此时删除倒数第 K 个节点等价于删除第 (num - k + 1) 个节点。

代码如下:

//节点
class Node{
    public int value;
    public Node next;
    public Node(int data) {
        this.value = data;
    }
}
//删除第K个节点
public Node removeLastKthNode(Node head, int K) {
        if(head == null || K < 1)
            return head;
        Node temp = head;
        int num = 0;
        while (temp != null) {
            num++;
            temp = temp.next;
        }
        if (num == K) {
            return head.next;
        }
        if (num > K) {
            temp = head;
            //删除第(num-k+1)个节点
            //定位到这个点的前驱
            while (num - K != 0) {
                temp = temp.next;
                num--;
            }
            temp.next = temp.next.next;
        }
        return head;
    }

原文发布于微信公众号 - 苦逼的码农(di201805)

原文发表时间:2018-11-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

10:大整数加法

10:大整数加法 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 求两个不超过200位的非负整数的和。 输入有两行,每...

487120
来自专栏陈树义

如何检测链表中存在的环

链表有环的定义是,链表的尾节点指向了链接中间的某个节点。比如下图,如果单链表有环,则在遍历时,在通过结点J之后,会重新回到结点D。 ? 看了上面的定义之后,如...

30260
来自专栏互联网技术杂谈

快速熟悉Java

参考著名的python快速入门(Quick Python Script Explanation for Programmers):https://mp.weix...

28390
来自专栏Fish

CUDA PTX ISA阅读笔记(二)

8. 第八章 指令集 这一章占了整个手册的一大半(百十来页吧),主要介绍各种指令,虽然页数很多,但是大多数指令都很简单。 8.1. 指令的形式和语义描述 这章就...

54350
来自专栏青玉伏案

算法与数据结构(十四) 堆排序 (Swift 3.0版)

上篇博客主要讲了冒泡排序、插入排序、希尔排序以及选择排序。本篇博客就来讲一下堆排序(Heap Sort)。看到堆排序这个名字我们就应该知道这种排序方式的特点,就...

255100
来自专栏大数据架构

UML(一) 类图详解

33960
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十八】Map接口集合详解

四、Map接口 Map与List、Set接口不同,它是由一系列键值对组成的集合,提供了key到Value的映射。同时它也没有继承Collecti...

37660
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之数值的整数次方(九度OJ1514)

题目描述: 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 输入: 输入可能包含多个测试样例。 ...

22370
来自专栏数据结构与算法

BZOJ2783: [JLOI2012]树(树上前缀和+set)

Description 数列 提交文件:sequence.pas/c/cpp 输入文件:sequence.in 输出文件:sequence.out 问题描述:...

29440
来自专栏calmound

uva Andy's First Dictionary

题目很简单,数组开大就好,5000但加上重复就不够了10000都小,sort排序前闭合后开,对二维字符窜排序用结构体,所以只有一组的时候只是本身但是不会出现RE...

35040

扫码关注云+社区

领取腾讯云代金券