前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【链表问题】删除单链表中的第K个节点

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

作者头像
帅地
发布2018-12-18 16:49:54
1.7K0
发布2018-12-18 16:49:54
举报
文章被收录于专栏:苦逼的码农

前言

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

【题目描述】

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

【要求】

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

【难度

【解答】

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

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

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

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

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

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

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

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

代码如下:

代码语言:javascript
复制
//节点
class Node{
    public int value;
    public Node next;
    public Node(int data) {
        this.value = data;
    }
}
代码语言:javascript
复制
//删除第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;
    }
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-11-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 帅地玩编程 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档